On the decoding of binary cyclic codes with the Newton identities

We revisit in this paper the concept of decoding binary cyclic codes with Gröbner bases. These ideas were first introduced by Cooper, then Chen, Reed, Helleseth and Truong, and eventually by Orsini and Sala. We discuss here another way of putting the decoding problem into equations: the Newton identities. Although these identities have been extensively used for decoding, the work was done manually, to provide formulas for the coefficients of the locator polynomial. This was achieved by Reed, Chen, Truong and others in a long series of papers, for decoding quadratic residue codes, on a case-by-case basis. It is tempting to automate these computations, using elimination theory and Gröbner bases.Thus, we study in this paper the properties of the system defined by the Newton identities, for decoding binary cyclic codes. This is done in two steps, first we prove some facts about the variety associated with this system, then we prove that the ideal itself contains relevant equations for decoding, which lead to formulas.Then we consider the so-called online Gröbner basis decoding, where the work of computing a Gröbner basis is done for each received word. It is much more efficient for practical purposes than preprocessing and substituting into the formulas. Finally, we conclude with some computational results, for codes of interesting length (about one hundred).     

Development of ‘UR-System 2’: a training system for recovery of motor function of plegic upper limb after stroke

We developed a new training system, called ‘UR-System 2’, for the recovery of motor function of a plegic upper limb after stroke. UR-System 2, which was redesigned based on knowledge gained from clinical tests using UR-System 1, was newly equipped with a function for testing the motor function of patients, such as isolated movement. In order to verify the effectiveness of UR-System 2, we conducted the following procedures: we verified the safety of training in healthy persons; we gathered standard data on pronation and supination of healthy forearms during tests; and, we verified that the test function was effective in evaluating the recovery effect of isolated movement in two hemiplegic patients.     

减少重建数据量的冗余编码技术研究

为防止硬件故障或机器宕机导致的数据丢失,冗余编码技术被广泛应用于分布式存储系统中来保证数据的可靠性。然而,传统的冗余编码技术,如里德-所罗门码,存在着重建数据量大的问题。副本技术在重建丢失数据时只需要读取和传输丢失的数据,而冗余编码需要读取和传输更大的数据量,从而消耗更多的磁盘I/O带宽和网络带宽。因此,基于冗余编码的分布式存储系统在重建数据时将消耗更长的时间,从而将整个系统长时间暴露在一种降级的模式下,进而增加了发生永久性数据丢失的风险。为解决这个问题,减少重建数据量的冗余编码技术不断被提出,然而只有这些冗余编码与传统的里德-所罗门码的比较,缺少它们在存储系统的综合比较。系统地从减少重建数据量等几个重要方面研究了这些减少重建数据量的冗余编码技术,从而为实际系统中采用合适的编码提供重要参考和依据。     

有限长度LDPC码一种速率兼容删余算法

提出一种AWGN信道下有限长度RC-LDPC码的删余算法,该算法对规则及非规则LDPC码均有效。该删余算法基于一系列准则,其中一个重要准则是某个候选删除节点的具有低的近似环外消息度(ACE)的短环的数量。仿真结果表明,ACE对删余码的性能有很大的影响,该算法的性能比已有算法有进一步提高。     

Restricted compositions and permutations: From old to new Gray codes

Any Gray code for a set of combinatorial objects defines a total order relation on this set: x is less than y if and only if y occurs after x in the Gray code list. Let ? denote the order relation induced by the classical Gray code for the product set (the natural extension of the Binary Reflected Gray Code to k-ary tuples). The restriction of ? to the set of compositions and bounded compositions gives known Gray codes for those sets. Here we show that ? restricted to the set of bounded compositions of an interval yields still a Gray code. An n-composition of an interval is an n-tuple of integers whose sum lies between two integers; and the set of bounded n-compositions of an interval simultaneously generalizes product set and compositions of an integer, and so ? put under a single roof all these Gray codes.As a byproduct we obtain Gray codes for permutations with a number of inversions lying between two integers, and with even/odd number of inversions or cycles. Such particular classes of permutations are used to solve some computational difficult problems.     

Cyclic codes over R = Fp + uFp +?+ uFp with length pn

In this paper, all cyclic codes with length p^sn, (n prime to p) over the ring R = F_p + uF_p +?+ u^k−1F_p are classified. It is first proved that Tor_j(C) is an ideal of , so that the structure of ideals over extension ring S_u^k(m,ω)=GR(u^k,m)[ω]/〈ω^ps-1〉 is determined. Then, an isomorphism between R[X]/〈X^N − 1〉 and a direct sum ⊕_h∈IS_u^k(m_h,ω) can be obtained using discrete Fourier transform. The generator polynomial representation of the corresponding ideals over F_p + uF_p +?+ u^k−1F_p is calculated via the inverse isomorphism. Moreover, torsion codes, MS polynomial and inversion formula are described.     

一种基于稳定子码的量子LDPC码的构造

本文在低密度奇偶校验码和稳定子码纠错理论基础上,分析了稳定子码的构造方法,提出了一种基于稳定子码的量子LDPC码的构造方法,并以(12,3)量子LDPC码为例说名该方法的有效性,最后对(32,12)和(64,24)码在退极化信道的性能表现进行了数值分析。     

On codes defined by bio-operations

We consider the classes of ⊕$\oplus$-codes and ⊗$\otimes$-codes, which are superclasses of outfix and hyper-codes, respectively. These restrictions are based on the synchronized insertion operation, which serves as a model for the gene rearrangement function in certain unicellular organisms. We investigate the classes of ⊕$\oplus$-codes and ⊗$\otimes$-codes from a theoretical perspective, examine their relationships with traditional code classes and consider related decidability problems.     

Performance of N-body codes on hybrid machines

N-body codes are routinely used for simulation studies of physical systems, e.g. in the fields of computational astrophysics and molecular dynamics. Typically, they require only a moderate amount of run-time memory, but are very demanding in computational power. A detailed analysis of an N-body code performance, in terms of the relative weight of each task of the code, and how this weight is influenced by software or hardware optimisations, is essential in improving such codes. The approach of developing a dedicated device, GRAPE [J. Makino, M. Taiji, Scientific Simulations with Special Purpose Computers, Wiley, New York, 1998], able to provide a very high performance for the most expensive computational task of this code, has resulted in a dramatic performance leap. We explore on the performance of different versions of parallel N-body codes, where both software and hardware improvements are introduced. The use of GRAPE as a ‘force computation accelerator’ in a parallel computer architecture, can be seen as an example of a hybrid architecture, where special purpose device boards help a general purpose (multi)computer to reach a very high performance.     

量子LDPC码在量子密钥分配中的应用

首先将BB84密钥分配协议等价成一个特殊的Wire-tap信道模型,即主信道是比特翻转率为0.25ε的二进制对称信道,窃听信道是删除概率为(1-ε)的二进制删除信道;然后利用量子LDPC码CSS(C1,C2)的编码方法和性质实现BB84协议下的Wire-tap信道的安全通信,同时证明了BB84协议的安全性;最后,通过计算该特殊的Wire-tap信道的安全容量,得到了基于量子LDPC码的BB84协议的可容忍误码率.