Perfect Codes From Cayley Graphs Over Lipschitz Integers

The search for perfect error-correcting codes has received intense interest since the seminal work by Hamming. Decades ago, Golomb and Welch studied perfect codes for the Lee metric in multidimensional torus constellations. In this work, we focus our attention on a new class of four-dimensional signal spaces which include tori as subcases. Our constellations are modeled by means of Cayley graphs defined over quotient rings of Lipschitz integers. Previously unexplored perfect codes of length one will be provided in a constructive way by solving a typical problem of vertices domination in graph theory. The codewords of such perfect codes are constituted by the elements of a principal (left) ideal of the considered quotient ring. The generalization of these techniques for higher dimensional spaces is also considered in this work by modeling their signal sets through Cayley-Dickson algebras.     

Reconstructing Extended Perfect Binary One-Error-Correcting Codes From Their Minimum Distance Graphs

The minimum distance graph of a code has the codewords as vertices and edges exactly when the Hamming distance between two codewords equals the minimum distance of the code. A constructive proof for reconstructibility of an extended perfect binary one-error-correcting code from its minimum distance graph is presented. Consequently, inequivalent such codes have nonisomorphic minimum distance graphs. Moreover, it is shown that the automorphism group of a minimum distance graph is isomorphic to that of the corresponding code.      

一种基于循环移位矩阵的LDPC码构造方法

具有准循环结构的低密度奇偶校验码(QC-LDPC Codes)是目前被广泛采用的一类LDPC码。本文提出了一种结合PEG算法构造基于循环移位矩阵的QC-LDPC码的方法。该方法首先将QC-LDPC码传统的基于比特的二分图简化为基于Block的二分图,然后在该图中采用PEG算法遵循的环路最大原则确定每一个循环移位矩阵的位置,最后根据QC-LDPC码的环路特性为每一个循环移位矩阵挑选循环移位偏移量。利用该算法,本文构造了长度从1008bit到8064bit,码率从1/2到7/8各种参数的LDPC码。仿真结果表明,本文构造的LDPC码性能优于目前采用有限几何、两个信息符号的RS码、组合数学等常用的代数方法构造的QC-LDPC码。     

低秩循环矩阵的构造方法及其关联的多元LDPC码

在图像处理中,低秩矩阵的冗余信息可用于图像恢复和图像特征提取,而在迭代译码中,校验矩阵的冗余行可以加快译码收敛速度。该文研究一类易于硬件实现的低秩循环矩阵。首先将循环矩阵转换为位置集合,并基于同构理论简化了位置集合的搜索空间,从而基于比特移位方法提出了循环矩阵的构造方法。考虑非零域元素的列赋值与矩阵秩之间的关系,选取Tanner图中没有长度为4的环的循环矩阵,基于非零域元素的列赋值思想提出了不同阶数、不同码率的多元LDPC码构造方法。数值仿真结果表明,与基于PEG算法构造的二元LDPC码比较,所构造的多元LDPC码在BPSK调制方式下在误码字率10^–5附近有0.9 dB的增益;在与高阶调制相结合时,有更大的性能提升。此外,所构造的多元LDPC码在迭代5次与50次下的性能几乎一致,这为低时延高可靠通信提供了一种有效的候选编码方案。     

低秩循环矩阵的构造方法及其关联的多元LDPC码

在图像处理中,低秩矩阵的冗余信息可用于图像恢复和图像特征提取,而在迭代译码中,校验矩阵的冗余行可以加快译码收敛速度.该文研究一类易于硬件实现的低秩循环矩阵.首先将循环矩阵转换为位置集合,并基于同构理论简化了位置集合的搜索空间,从而基于比特移位方法提出了循环矩阵的构造方法.考虑非零域元素的列赋值与矩阵秩之间的关系,选取Tanner图中没有长度为4的环的循环矩阵,基于非零域元素的列赋值思想提出了不同阶数、不同码率的多元LDPC码构造方法.数值仿真结果表明,与基于PEG算法构造的二元LDPC码比较,所构造的多元LDPC码在BPSK调制方式下在误码字率10-5附近有0.9 dB的增益;在与高阶调制相结合时,有更大的性能提升.此外,所构造的多元LDPC码在迭代5次与50次下的性能几乎一致,这为低时延高可靠通信提供了一种有效的候选编码方案.     

中短长度LT码的展开图构造方法

该文提出了中短长度LT码的展开图构造方法。该方法以输出节点为根展开Tanner图,当满足停止准则后,随机选择未被覆盖或最深展开层的输入节点与根相连。展开图法通过展开深度门槛和最大可展深度两个参数的设置,在控制短环的基础上, 在尽可能大的范围内随机地选择输入节点。仿真结果表明,该方法与随机图等方法相比,能够有效地改善中短长度LT码的性能。     

基于图的非二元非对称量子码构造(英文)

The theory of quantum error correcting codes is a primary tool for fighting decoherence and other quantum noise in quantum communication and quantum computation. Recently, the theory of quantum error correcting codes has developed rapidly and been extended to protect quantum information over asymmetric quantum channels, in which phase-shift and qubit-flip errors occur with different probabilities. In this paper, we generalize the construction of symmetric quantum codes via graphs (or matrices) to the asymmetric case, converting the construction of asymmetric quantum codes to finding matrices with some special properties. We also propose some asymmetric quantum Maximal Distance Separable (MDS) codes as examples constructed in this way.     

基于二分图的乘积码迭代译码算法

该文给出了由汉明分量乘积码构造广义低密度(GLD)码的一般方法。基于所得稀疏矩阵的二分图,并结合分组码与低密度校验(LDPC)码的译码算法,设计出一种新颖的可用于乘积码迭代译码的Chase-MP算法。由于所得二分图中不含有长度为4和6的小环,因而大大减少图上迭代时外信息之间的相关性,进而提高译码性能。对加性高斯白噪声(AWGN)及瑞利(Rayleigh)衰落信道下,汉明分量 (63,57,3)2 乘积码的模拟仿真显示,该算法能够获得很好的译码性能。与传统的串行迭代Chase-2算法相比,Chase-MP算法适合用于全并行译码处理,便于硬件实现,而且译码性能优于串行迭代Chase-2算法。     

A General Construction of Inter-Group Complementary Codes Based on Z-Complementary Codes and Perfect Periodic Cross-Correlation Codes

In this paper, a new construction of inter-group complementary (IGC) codes is proposed based on Z-complementary codes and perfect periodic cross-correlation (PPCC) codes. The correlation properties of the new generated IGC codes are as follows: (1) the autocorrelation sidelobe values of the codes are zeros in the zero correlation zone (ZCZ), (2) the cross-correlation values between different codes in the same group are zeros in the ZCZ, (3) the cross-correlation values between codes of different groups are zeros during the whole period. Comparing to the existed IGC codes, the ZCZ length of the generated IGC codes can be predefined flexibly; the number of groups and the number of codes in each group have more freedom according to the advantages of Z-complementary codes and PPCC codes.     

关于双完备认证码的特征

本文刻画了双完备认证码的结构,给出了r阶完备认证码的定义,并给出判定r阶完备认证码的一个充要条件,由组合设计构造了r阶完备认证码。     

完备的具有仲裁的认证码的组合特征

具有仲裁的认证码既要防止发方和收方的互相期骗,又要防止敌手的欺骗,本文安全刻划了完备的具有仲裁的认证码的组合特征。     

Constructions for Perfect 5-Deletion-Correcting Codes of Length$7$

There are two kinds of perfect (k-t)-deletion-correcting codes with words of length k over an alphabet of size v, those where the coordinates may be equal and those where all coordinates must be different. We call these two kinds of codes T*(t,k,v)-codes and T(t,k,v)-codes respectively. Both a T*(t,k,v)-code and a T(t,k,v)-code are capable of correcting any combination of up to (k-t) deletions and insertions of letters occurred in transmission of codewords. In this correspondence, we consider constructions for the codes from directed designs. By means of these constructions, the existence of a T(2,7,v)-code is settled for all positive integers v with the exception of 68 values of v; T^*(2,7,v)-codes are constructed for all integers vges2350. A large number of explicit constructions for T^*(2,7,v)-codes with v<2350 are also presented     

Perfect Space&#8211;Time Block Codes

In this paper, we introduce the notion of perfect space-time block codes (STBCs). These codes have full-rate, full-diversity, nonvanishing constant minimum determinant for increasing spectral efficiency, uniform average transmitted energy per antenna and good shaping. We present algebraic constructions of perfect STBCs for 2, 3, 4, and 6 antennas     

On the Existence of Perfect Space–Time Codes

Perfect space-time codes are codes for the coherent multiple-input multiple-output (MIMO) channel. They have been called so since they satisfy a large number of design criteria that makes their performances outmatch many other codes. In this correspondence, we discuss the existence of such codes (or more precisely, the existence of perfect codes with optimal signal complexity).     

LDPC码在因子图上的构造及其译码

LDPC码是一种可以接近香农限的线性分组码,可通过稀疏奇偶校验矩阵来构造。也可以用因子图来构成。根据LDPC码的不同构成方法至今已提出了数种不同的译码方法。本文介绍了基于因子图的LDPC码的构造方法,分析了和一积(SPA)译码算法的基本原理,最后详细讨论了用SPA算法对LDPC码进行译码的过程。     

Constraint Complexity of Realizations of Linear Codes on Arbitrary Graphs

A graphical realization of a linear code C consists of an assignment of the coordinates of C to the vertices of a graph, along with a specification of linear state spaces and linear "local constraint" codes to be associated with the edges and vertices, respectively, of the graph. The kappa-complexity of a graphical realization is defined to be the largest dimension of any of its local constraint codes, kappa -complexity is a reasonable measure of the computational complexity of a sum-product decoding algorithm specified by a graphical realization. The main focus of this paper is on the following problem: given a linear code C and a graph G, how small can the kappa-complexity of a realization of C on G be? As useful tools for attacking this problem, we introduce the vertex-cut bound, and the notion of "vc-treewidth" for a graph, which is closely related to the well-known graph-theoretic notion of treewidth. Using these tools, we derive tight lower bounds on the kappa-complexity of any realization of C on G. Our bounds enable us to conclude that good error-correcting codes can have low-complexity realizations only on graphs with large vc-treewidth. Along the way, we also prove the interesting result that the ratio of the kappa-complexity of the best conventional trellis realization of a length-n code C to the kappa-complexity of the best cycle-free realization of C grows at most logarithmically with code length n. Such a logarithmic growth rate is, in fact, achievable.     

On Decoding Binary Perfect and Quasi-Perfect Codes over Markov Noise Channels

We study the decoding problem when a binary linear perfect or quasi-perfect code is transmitted over a binary channel with additive Markov noise. After examining the properties of the channel block transition distribution, we derive sufficient conditions under which strict maximum-likelihood decoding is equivalent to strict minimum Hamming distance decoding when the code is perfect. Additionally, we show a near equivalence relationship between strict maximum likelihood and strict minimum distance decoding for quasi-perfect codes for a range of channel parameters and the code's minimum distance. As a result, an improved (complete) minimum distance decoder is proposed and simulations illustrating its benefits are provided.     

基于二分图低密度奇偶校验码围长计算方法

对于任意给定的低密度奇偶校验（LDPC）码,快速计算其围长具有重要意义。通过对基于二分图LDPC码围长计算方法进行研究,提出了一种快速计算围长并能给出各校验节点（或信息节点）上经过的最短环个数的算法。通过MATLAB仿真测试表明,该算法对于PEGReg504x1008这样大规模的LDPC码Ⅳ矩阵,只需2．876s即可计算出该码的围长和各校验节点上经过的最短环个数,更说明该算法具有快速计算围长的能力。     

基于完备循环差集的QC-LDPC码的确定性构造

针对准循环低密度奇偶校验(Quasi-Cyclic Low-Density Parity Check,QC-LDPC)码中存在编码复杂度高且码率码长选择不灵活等问题,基于完备循环差集(Perfect Cyclic Difference Sets,PCDS)提出了一种确定性的构造方法.基矩阵(Base Matrix,BM)中的移位次数可由完备循环差集经过简单的加减运算获得,特殊结构的基矩阵和完备循环差集结合,节省了存储空间,降低了硬件实现的复杂度,其围长至少为6,且码长码率可灵活选择.仿真结果表明:在加性高斯白噪声(Additive White Gauss Noise,AWGN)信道下采用和积算法(Sum-Product Algorithm,SPA)迭代译码,码率为0.5、误码率为10-6时,构造的基于完备循环差集的非规则PCDS-QC-LDPC(2680,1340)码比基于PEG-QC-LDPC(2680,1340)码和掩模的离散数组AD-MASK-QC-LDPC(2680,1340)码的净编码增益(Net Coding Gain,NCG)分别提高了0.13和0.32 dB.