Flexible forward error correction codes with application to partial media data recovery

Conventionally, linear block codes designed for packet erasure correction are targeted to recover all the lost source packets per block, when the fraction of lost data is smaller than the redundancy overhead. However, these codes fail to recover any lost packets, if the number of erasures just exceeds the limit for full recovery capability, while it can still be beneficial to recover part of the symbols. In addition, common linear block codes are not well suited for unequal error protection, since different block codes with different rates must be allocated for each priority class separately. These two problems motivate the design of more flexible forward error correction (FEC) codes for media streaming applications. We first review the performance of short and long linear block codes. Long block codes generally offer better error correction capabilities, but at the price of higher complexity and larger coding delay. Short block codes can be more appropriate in media streaming applications that require smooth performance degradation when the channel loss rate increases. We study a new class of linear block codes using sparse generator matrices that permit to optimize the performance of short block codes for partial recovery of the lost packets. In addition, the proposed codes are extended to the design of unequal erasure protection solutions. Simulations of practical video streaming scenarios demonstrate that the flexible sparse codes offer a promising solution with interesting error correction capabilities and small variance in the residual loss rate. They typically represent an effective trade-off between short block codes with limited flexibility, and long block codes with delay penalties.     

DC-free coset codes

A class of block coset codes with disparity and run-length constraints are studied. They are particularly well suited for high-speed optical fiber links and similar channels, where DC-free pulse formats, channel error control, and low-complexity encoder-decoder implementations are required. The codes are derived by partitioning linear block codes. The encoder and decoder structures are the same as those of linear block codes with only slight modifications. A special class of DC-free coset block codes are derived from BCH codes with specified bounds on minimum distance, disparity, and run length. The codes have low disparity levels (a small running digital sum) and good error-correcting capabilities     

Partitioned linear block codes for computer memory with 'stuck-at' defects

Linear block codes are studied for improving the reliability of message storage in computer memory with stuck-at defects and noise. The case when the side information about the state of the defects is available to the decoder or to the encoder is considered. In the former case, stuck-at cells act as erasures so that techniques for decoding linear block codes for erasures and errors can be directly applied. We concentrate on the complimentary problem of incorporating stuck-at information in the encoding of linear block codes. An algebraic model for stuck-at defects and additive errors is presented. The notion of a "partitioned" linear block code is introduced to mask defects known at the encoder and to correct random errors at the decoder. The defect and error correction capability of partitioned linear block codes is characterized in terms of minimum distances. A class of partitioned cyclic codes is introduced. A BCH-type bound for these cyclic codes is derived and employed to construct partitioned linear block codes with specified bounds on the minimum distances. Finally, a probabilistic model for the generation of stuck-at cells is presented. It is shown that partitioned linear block codes achieve the Shannon capacity for a computer memory with symmetric defects and errors.     

关于线性分组码的不可检错误概率

本文给出了检错好码的定义,证明了GF(2)上的(n,k)线性分组码为检错好码的充要条件是其对偶码也为检错好码。文中还得到了关于检错好码的一系列新的结果。对二元(n,k)线性分组码,我们给出了不可检错误概率新的下限。这些限只与n和k有关,而与码的重量结构无关。     

线性分组码与时空分组码级联的迭代译码

提出了线性分组码与时空分组码的级联编码方案,推导了时空分组码在比特级上的软输入软输出译码算法,进而给出了在线性分组码和时空分组码之间进行迭代译码的算法。仿真结果表明这种方案与现有方案相比在能够获得最大分集增益的同时还能获得更大的编码增益。     

关于几类线性分组码网格图复杂度的研究

本文研究了几类线性分组码C[n,k,d]的网格图复杂度s（C）。给出并证明了码长为奇数的两类线性分组码的网格图复杂度。同时得出了有关可纠t个错的本原BCH码[2^m-1,2^m-1-mt]及其扩展本在BCH码的网格图复杂度的若干结论。从而避免了必须先寻找码的直和结构才可得到码的网格图复杂度的较好上界。     

New multilevel codes over GF(q)

Set partitioning is applied to multidimensional signal spaces over GF(q), i.e., GFⁿ¹(q) (n1⩽q ), and it is shown how to construct both multilevel block codes and multilevel trellis codes over GF(q). Multilevel (n, k, d) block codes over GF(q) with block length n, number of information symbols k, and minimum distance d_min⩾d are presented. These codes use Reed-Solomon codes as component codes. Longer multilevel block codes are also constructed using q-ary block codes with block length longer than q+1 as component codes. Some quaternary multilevel block codes are presented with the same length and number of information symbols as, but larger distance than, the best previously known quaternary one-level block codes. It is proved that if all the component block codes are linear. the multilevel block code is also linear. Low-rate q-ary convolutional codes, word-error-correcting convolutional codes, and binary-to-q-ary convolutional codes can also be used to construct multilevel trellis codes over GF(q) or binary-to-q-ary trellis codes     

软判决译码研究进展

本文综述了软判决译码研究的发展概况，全文分四部分。第一部分简单地回顾了构造Ｓｈａｎｎｏｎ码的发展概况；第二部分在前一部分基础上叙述了线性分组码软判决译码的一般研究的状况；第三部分讨论了基于网络图上的线性分组码软判决译码的发展概况；最后描述了Ｔｒｕｂｏ码与迭代反馈软判决译码的研究状况与今后的发展方向     

Tailbiting codes: bounds and search results

Tailbiting trellis representations of linear block codes with an arbitrary sectionalization of the time axis are studied. The notations of regular and irregular tailbiting codes are introduced and their maximal state complexities are lower-bounded. The asymptotic behavior of the derived bound is investigated. Furthermore, for regular tailbiting codes the product state complexity is lower-bounded. Tables of new tailbiting trellis representations of linear block codes of rates 1/2, 1/3, and 1/4 are presented. Almost all found trellises are optimal in the sense of the new bound on the state complexity and for most codes with nonoptimal trellises there exist time-varying trellises which are optimal. Five of our newly found tailbiting codes are better than the previously known linear codes with the same parameters. Four of them are also superior to any previously known nonlinear code with the same parameters. Also, more than 40 other quasi-cyclic codes have been found that improve the parameter set of previously known quasi-cyclic codes     

几类格的快速译码

本文通过研究16维Barnes-Wall格和基于构造A的二元线性分组码、四元线性分组码的导出格的代数结构,将这些格的译码问题转化为在相应码的格图上求最短路径的问题,从而提出了这些格的快速译码算法,并分析了译码算法的时间复杂性。     

Linear block codes for nonindependent errors

A computerised search procedure based on certain properties of the parity-check matrix of those block codes capable of correcting nonindependent errors is described which yields a considerable number of linear block codes that are capable of correcting random or burst errors.     

Linear uniform codes

Linear uniform codes are linear codes with minimum distance equal to average distance, and hence are optimum from minimum-distance point of view. A unified approach to block and convolutional codes is taken, leading to a simpler encoder for convolutional uniform codes.     

Tightened Upper Bounds on the ML Decoding Error Probability of Binary Linear Block Codes

The performance of maximum-likelihood (ML) decoded binary linear block codes is addressed via the derivation of tightened upper bounds on their decoding error probability. The upper bounds on the block and bit error probabilities are valid for any memoryless, binary-input and output-symmetric communication channel, and their effectiveness is exemplified for various ensembles of turbo-like codes over the additive white Gaussian noise (AWGN) channel. An expurgation of the distance spectrum of binary linear block codes further tightens the resulting upper bounds     

Binary codes with disjoint codebooks and mutual Hamming distance

Equal-length linear binary block error-control codes with disjoint codebooks and mutual Hamming distance are considered. A method of constructing pairs of these disjoint codes from known cyclic codes, and determining their mutual distance, is described. Some sets of length-15 cyclic codes are tabulated.     

Iterative reliability-based decoding of linear block codes with adaptive belief propagation

In this letter, an iterative decoding algorithm for linear block codes combining reliability-based decoding with adaptive belief propagation decoding is proposed. At each iteration, the soft output values delivered by the adaptive belief propagation algorithm are used as reliability values to perform reduced order reliability-based decoding of the code considered. This approach allows to bridge the gap between the error performance achieved by the lower order reliability-based decoding algorithms which remain sub-optimum, and the maximum likelihood decoding, which is too complex to be implemented for most codes employed in practice. Simulations results for various linear block codes are given and elaborated.     

Multichannel convolutional coding systems over a direct sum of Galois fields

Classes of codes for a multichannel communication system are considered. A fast algorithm is developed to calculate syndromes of multichannel linear systematic codes, including both block and convolutional codes, by using a direct sum of Galois fields.     

On linear structure and phase rotation invariant properties ofblock M-PSK modulation codes

Two important structural properties of block M(=2^' )-ary PSK modulation codes, linear structure and phase symmetry, are investigated. An M-ary modulation code is first represented as a code with symbols from the integer group S_M-PSK=(0,1,2,---,M-1) under modulo-M addition. Then the linear structure of block M-PSK modulation codes over S_M-PSK with respect to modulo- M vector addition is defined, and conditions are derived under which a block M-PSK modulation code is linear. Once the linear structure is developed, the phase symmetry of block M-PSK modulation codes is studied. In particular, a necessary and sufficient condition for a block M-PSK modulation code that is linear as a binary code to be invariant under 2^h/180°M phase rotation, for 1⩽h⩽l is derived. Finally, a list of short 8-PSK and 16-PSK modulation codes is given, together with their linear structure and the smallest phase rotation for which a code is invariant     

On block-coded modulation using unequal error protection codes overRayleigh-fading channels

This paper considers block-coded 8-phase-shift-keying (PSK) modulations for the unequal error protection (UEP) of information transmitted over Rayleigh-fading channels. Both conventional linear block codes and linear UEP (LUEP) codes are combined with a naturally labeled 8-PSK signal set, using the multilevel construction of Imai and Hirakawa (1977). Computer simulation results are presented showing that, over Rayleigh-fading channels, it is possible to improve the coding gain for the most significant bits with the use of binary LUEP codes as constituent codes, in comparison with using conventional binary linear codes alone     

Noncoherent block-coded MPSK

For coherent detection, block-coded modulation is a bandwidth efficient scheme. In this paper, we propose theorems about the error performance of block-coded modulation using M-ary phase-shift keying (MPSK) for noncoherent detection. Based on these theorems, we propose a novel block-coded modulation scheme for noncoherent detection called noncoherent block-coded MPSK. The proposed scheme provides flexible designs of noncoherent block codes with different code rate, block length and error performance. Good noncoherent block codes can be easily obtained by properly choosing binary linear block codes as the component codes. Moreover, noncoherent block codes of this new scheme can be decoded by multistage decoding, which has the advantage of low complexity and satisfactory error performance. In this paper, two algorithms of multistage decoding for noncoherent detection are proposed as well. The error performance of some designed codes and decoding algorithms is verified by computer simulation.     

On the symmetry of good nonlinear codes

It is shown that there are arbitrarily long "good" (in the sense of Gilbert) binary block codes that are preserved under very large permutation groups. This result contrasts sharply with the properties of linear codes: it is conjectured that long cyclic codes are bad, and known that long affine-invariant codes are bad.