Approaching blokh-zyablov error exponent with linear-time encodable/decodable codes

Guruswami and Indyk showed in [1] that Forney?s error exponent can be achieved with linear coding complexity over binary symmetric channels. This paper extends this conclusion to general discrete-time memoryless channels and shows that Forney?s and Blokh-Zyablov error exponents can be arbitrarily approached by one-level and multi-level concatenated codes with linear encoding/decoding complexity. The key result is a revision to Forney?s general minimum distance decoding algorithm, which enables a low complexity integration of Guruswami-Indyk?s outer codes into the concatenated coding schemes.     

'Diffuse' threshold decodable rate 1/2 convolutional codes

This paper shows the existence (by construction) of ratefrac{1}{2}convolutional codes that correct bursts of lengthBortrandom errors. The codes have memory length and guard space requirements that are asymptotically4Band minimal effective length. Kohlenberg introduced the term "diffuse code" for his two random-error or single-burst error-correcting codes with minimal effective length and both a memory and guard-space requirement of3B + 1. To this point, there does not seem to be any procedure for finding codes with minimal effective length and guard space requirements asymptotically3B.     

On efficient majority logic decodable codes

A particular shortening technique is applied to majority logic decodable codes of length2^{t}. The shortening technique yields new efficient codes of lengthsn = 2^{p}, wherepis a prime, e.g., a (128,70) code withd_{maj} = 16. For moderately long code lengths (e.g.,n = 2^{11} or 2^{13}), a 20-25 percent increase in efficiency can be achieved over the best previously known majority logic decodable codes. The new technique also yields some efficient codes for lengthsn = 2^{m}wheremis a composite number, for example, a (512,316) code withd_{maj} = 32code which has 42 more information bits than the previously most efficient majority logic decodable code.     

Easily decodable efficient self-orthogonal block codes

A class of self-orthogonal block codes is described, which are easy to decode and to augments. They are constructed by forming parity-check equations across certain patterns of information digits arranged in a 2-dimensional array. The codes are of a rate close to the optimum for self-othogonal codes.     

Easily decodable binary cyclic codes

This paper presents a class of binary cyclic codes with block length n = 2^m? 1, having n?k = 2^m? parity checks and a minimum distance d=m +1, where m is an integer. These codes are shown to be majority logic decodable in one step by making use of the concept of a quasi-perfect finite difference set.     

Class of majority decodable real-number codes

A majority decoding algorithm for a class of real-number codes is presented. Majority decoding has been a relatively simple and fast decoding technique for codes over finite fields. When applied to decode real-number codes, the robustness of the majority decoding to the presence of background noise, which is usually an annoying problem for existing decoding algorithms for real-number codes, is its most prominent property. The presented class of real-number codes has generator matrices similar to those of the binary Reed-Muller codes and is decoded by similar majority logic     

Uniquely decodable codes for deterministic relay channels

The deterministic relay channel is analyzed and explicit code constructions for all binary and all ternary/binary channels are given. An explicit set of equivalence conditions is used to make a classification of all such relay channels, for which also the capacity is evaluated. The coding problem is then reduced to finding all possible output sequences of a certain finite-state channel determined by the relay coding strategy. The channel states correspond to the possible relay memory contents. For some relay channels capacity is reached by using simple uniquely decodable codes, thus establishing the zero-error capacity of those channels with finite-memory relay strategies. For other relay channels the relay memory must be arbitrarily large to achieve zero-error rates arbitrarily close to capacity. One such code construction is given. It is not known whether there exist relay channels for which the zero-error capacity is strictly smaller than the average-error capacity. The code construction problem for the semideterministic relay channel and for the nonsynchronized relay channel is briefly considered     

On a class of majority-logic decodable cyclic codes

A new infinite class of cyclic codes is studied. Codes of this class can be decoded in a step-by-step manner, using` majority logic. Some previously known codes fall in this class, and thus admit simpler decoding procedures. As random error-correcting codes, the codes are nearly as powerful as the Bose-Chaudhuri codes.     

On the construction of bounded-delay encodable codes forconstrained systems

We present a new technique to construct sliding-block modulation codes with a small decoding window. Our method, which involves both state splitting and look-ahead encoding, crucially depends on a new “local” construction method for bounded-delay codes. We apply our method to construct several new codes, all with a smaller decoding window than previously known codes for the same constraints at the same rate     

Design of efficiently encodable moderate-length high-rate irregular LDPC codes

This paper presents a new class of irregular low-density parity-check (LDPC) codes of moderate length (10/sup 3//spl les/n/spl les/10/sup 4/) and high rate (R/spl ges/3/4). Codes in this class admit low-complexity encoding and have lower error-rate floors than other irregular LDPC code-design approaches. It is also shown that this class of LDPC codes is equivalent to a class of systematic serial turbo codes and is an extension of irregular repeat-accumulate codes. A code design algorithm based on the combination of density evolution and differential evolution optimization with a modified cost function is presented. Moderate-length, high-rate codes with no error-rate floors down to a bit-error rate of 10/sup -9/ are presented. Although our focus is on moderate-length, high-rate codes, the proposed coding scheme is applicable to irregular LDPC codes with other lengths and rates.     

New construction of majority logic decodable quasicyclic codes

A new construction of majority logic decodable quasicyclic codes is presented. As an example, an infinite family of quasicyclic codes with a minimum distance of four is constructed, and comparisons are made to show that they are better than selforthogonal quasicyclic codes and Shiva codes.<>     

New family of binary one-step majority-logic decodable codes

One-step completely orthogonalisable binary codes derived from block designs are presented and their decoder structure is given.<>     

On binary majority-logic decodable codes (Corresp.)

LetVprimebe a binary(n,k)majority-logic decodable code withgprime (X)as its generator polynomial and odd minimum distanced. LetVbe the(n, k - 1)subset code generated bygprime (X)(1 + X). This correspondence shows thatVis majority-logic deeodable withd + 1orthogonal estimates. This fact is useful in the simultaneous correction of random errors and erasures.     

一种适用于大数逻辑可译LDPC码的自适应译码算法

大数逻辑可译低密度奇偶校验(LDPC)码是一类具有较大列重的码,针对此类特殊的LDPC码,提出了一种基于整数可靠度的低复杂度自适应译码算法。在译码的过程中,算法对每个校验节点分别引入不同的自适应修正因子对外信息进行修正。仿真表明提出的自适应译码算法的性能与和积译码算法的性能相当,在误码率(BER)约为10-5时两种算法性能之间仅有0.1 d B的差异。所提算法具有复杂度低、可并行操作、全整数的信息传递等优点,十分有利于工程实现。     

A class of high-speed decodable burst-correcting codes (Corresp.)

A class of high-speed decodable burst-correcting codes is presented. This class of codes is obtained by modifying burst-correcting convolutional codes into block codes and does not require any cyclic shifts in the decoding process. With the appropriate choices of parameters, the codes can approximate minimum-redundancy codes. The high-speed decodability is expected to make these codes suitable for application to computer systems.     

On the construction of a class of majority-logic decodable codes

The attractiveness of majority-logic decoding is its simple implementation. Several classes of majority-logic decodable block codes have been discovered for the past two decades. In this paper, a method of constructing a new class of majority-logic decodable block codes is presented. Each code in this class is formed by combining majority-logic decodable codes of shorter lengths. A procedure for orthogonalizing codes of this class is formulated. For each code, a lower bound on the number of correctable errors with majority-logic decoding is obtained. An upper bound on the number of orthogonalization steps for decoding each code is derived. Several majority-logic decodable codes that have more information digits than the Reed-Muller codes of the same length and the same minimum distance are found. Some results presented in this paper are extensions of the results of Lin and Weldon [11] and Gore [12] on the majority-logic decoding of direct product codes.     

Iteratively decodable codes from orthogonal arrays for optical communication systems

A novel family of low-density parity-check codes is proposed based on orthogonal arrays. Codes from this family have high code rate, girth of at least six, large minimum distance, and significantly outperform the error correction schemes based on turbo product codes proposed for optical communication systems.     

A note on one-step majority-logic decodable codes (Corresp.)

Construction of shortened geometric codes as Shown here results in 1-step majority-logic deeodable codes. The shortened codes retain the error-correction ability of the parent codes and the decoders for the shortened codes are much simpler than for the parent code. A table of shortened codes is given.     

MacNeish-Mann theorem based iteratively decodable codes for optical communication systems

A novel family of low-density parity-check codes is proposed based on MacNeish-Mann theorem for construction of mutually orthogonal Latin squares. Codes from this family have high code rate, girth at least six, large minimum distance, and significantly outperform conventional forward error correction schemes based on Reed-Solomon (RS) and turbo codes.     

Projective-plane iteratively decodable block codes for WDM high-speed long-haul transmission systems

Low-density parity-check (LDPC) codes are excellent candidates for optical network applications due to their inherent low complexity of both encoders and decoders. A cyclic or quasi-cyclic form of finite geometry LDPC codes simplifies the encoding procedure. In addition, the complexity of an iterative decoder for such codes, namely the min-sum algorithm, is lower than the complexity of a turbo or Reed-Solomon decoder. In fact, simple hard-decoding algorithms such as the bit-flipping algorithm perform very well on codes from projective planes. In this paper, the authors consider LDPC codes from affine planes, projective planes, oval designs, and unitals. The bit-error-rate (BER) performance of these codes is significantly better than that of any other known foward-error correction techniques for optical communications. A coding gain of 9-10 dB at a BER of 10/sup -9/, depending on the code rate, demonstrated here is the best result reported so far. In order to assess the performance of the proposed coding schemes, a very realistic simulation model is used that takes into account in a natural way all major impairments in long-haul optical transmission such as amplified spontaneous emission noise, pulse distortion due to fiber nonlinearities, chromatic dispersion, crosstalk effects, and intersymbol interference. This approach gives a much better estimate of the code's performance than the commonly used additive white Gaussian noise channel model.