| 1. |
- Anderson, John B, et al.
(författare)
-
On the BCJR algorithm for rate-distortion source coding
- 2007
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 53:9, s. 3201-3207
-
Tidskriftsartikel (refereegranskat)abstract
- The BCJR algorithm is an important channel decoding method. We extend it to trellis rate-distortion data compression. Beginning from source coding principles, the derivation of the algorithm avoids channel coding or soft output ideas. The encoder does not use entropy coding; equiprobable reproducer letters are emphasized since these maximize entropy. The BCJR method is demonstrated by tests of a tailbiting variant. It performs much better than the ordinary Viterbi algorithm for short and medium blocks. However, the improvement stems from tailbiting; the role of the BCJR is to achieve tailbiting in a relatively simple way. Some issues that arise with tailbiting are explored. It is shown that there is an optimal trellis state size for each block length.
|
|
| 2. |
- Anderson, John B
(författare)
-
On the complexity of bounded distance decoding for the AWGN channel
- 2002
-
Ingår i: IEEE Transactions on Information Theory. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9448. ; 48:5, s. 1046-1060
-
Tidskriftsartikel (refereegranskat)abstract
- Earlier work has derived the storage complexity of the bounded distance decoder (BDD) for binary-channel convolutional codes. We extend this work to the Gaussian noise channel and to partial-response codes. We show that the storage requirement similar to(2(1-R) - 1)(-t) paths for rate-R convolutional codes over the binary channel becomes similar to2(2Rt) over the Gaussian channel, where the decoder must correct t errors. Thus, convolutional coding over the Gaussian channel is not only 3 dB more energy efficient, but its decoding is simpler as well. Next, we estimate the path storage for partial-response codes, i.e., real-number convolutional codes, over the Gaussian channel. The growth rate depends primarily on the bandwidth of the code. A new optimization procedure is devised to measure the maximum storage requirement in Gaussian noise for these two code types. An analysis based on difference equations predicts the asymptotic storage growth for partial response codes.
|
|
| 3. |
- Battaglioni, Massimo, et al.
(författare)
-
Girth Analysis and Design of Periodically Time-Varying SC-LDPC Codes
- 2021
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 67:4, s. 2217-2235
-
Tidskriftsartikel (refereegranskat)abstract
- Time-varying spatially coupled low-density parity-check (SC-LDPC) codes with very large period are characterized by significantly better error rate performance and girth properties than their time-invariant counterparts, but the number of parameters they require to be described is usually very large and unpractical. Time-invariant SC-LDPC codes, which can be seen as periodically time-varying codes with unitary period, are represented through a small number of parameters and designed exploiting few degrees of freedom, but their error rate performance and girth properties are sub-optimal. In this paper, we show that the limits of time-invariant SC-LDPC codes can be overcome by transforming them into time-varying SC-LDPC codes with very small period. In particular, we show that periodically time-varying SC-LDPC codes with small period may exhibit significantly better girth properties than the corresponding time-invariant codes by exploiting a larger number of degrees of freedom in the code design, which however scale at most linearly with the product of the code period and the size of the considered base matrix.
|
|
| 4. |
- Bocharova, Irina, et al.
(författare)
-
A BEAST for prowling in trees
- 2004
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 50:6, s. 1295-1302
-
Tidskriftsartikel (refereegranskat)abstract
- When searching for convolutional codes and tailbiting codes of high complexity it is of vital importance to use fast algorithms for computing their weight spectra, which corresponds to finding low-weight paths in their code trellises. This can be efficiently done by a combined search in both forward and backward code trees. A bidirectional efficient algorithm for searching such code trees (BEAST) is presented. For large encoder memories, it is shown that BEAST is significantly more efficient than comparable algorithms. BEAST made it possible to rind new convolutional and tailbiting codes that have larger free (minimum) distances than the previously best known codes with the same parameters. Tables of such codes are presented.
|
|
| 5. |
- Bocharova, Irina, et al.
(författare)
-
A Closed Form Expression for the Exact Bit Error Probability for Viterbi Decoding of Convolutional Codes
- 2012
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 58:7, s. 4635-4644
-
Tidskriftsartikel (refereegranskat)abstract
- In 1995, Best et al. published a formula for the exact bit error probability for Viterbi decoding of the rate R=1/2, memory m=1 (2-state) convolutional encoder with generator matrix G(D)=(1 1+D) when used to communicate over the binary symmetric channel. Their formula was later extended to the rate R=1/2, memory m=2 (4-state) convolutional encoder with generator matrix G(D)=(1+D^2 1+D+D^2) by Lentmaier et al. In this paper, a different approach to derive the exact bit error probability is described. A general recurrent matrix equation, connecting the average information weight at the current and previous states of a trellis section of the Viterbi decoder, is derived and solved. The general solution of this matrix equation yields a closed form expression for the exact bit error probability. As special cases, the expressions obtained by Best et al. for the 2-state encoder and by Lentmaier et al. for a 4-state encoder are obtained. The closed form expression derived in this paper is evaluated for various realizations of encoders, including rate R=1/2 and R=2/3 encoders, of as many as 16 states. Moreover, it is shown that it is straightforward to extend the approach to communication over the quantized additive white Gaussian noise channel.
|
|
| 6. |
- Bocharova, Irina, et al.
(författare)
-
An improved bound on the list error probability and list distance properties
- 2008
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 54:1, s. 13-32
-
Tidskriftsartikel (refereegranskat)abstract
- List decoding of binary block codes for the additive white Gaussian noise channel is considered. The output of a list decoder is a list of the $L$ most likely codewords, that is, the L signal points closest to the received signal in the Euclidean-metric sense. A decoding error occurs when the transmitted codeword is not on this list. It is shown that the list error probability is fully described by the so-called list configuration matrix, which is the Gram matrix obtained from the signal vectors forming the list. The worst-case list configuration matrix determines the minimum list distance of the code, which is a generalization of the minimum distance to the case of list decoding. Some properties of the list configuration matrix are studied and their connections to the list distance are established. These results are further exploited to obtain a new upper bound on the list error probability, which is tighter than the previously known bounds. This bound is derived by combining the techniques for obtaining the tangential union bound with an improved bound on the error probability for a given list. The results are illustrated by examples.
|
|
| 7. |
- Bocharova, Irina, et al.
(författare)
-
BEAST decoding of block codes obtained via convolutional codes
- 2005
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 51:5, s. 1880-1891
-
Tidskriftsartikel (refereegranskat)abstract
- BEAST is a bidirectional efficient algorithm for searching trees. In this correspondence, BEAST is extended to maximum-likelihood (ML) decoding of block codes obtained via convolutional codes. First it is shown by simulations that the decoding complexity of BEAST is significantly less than that of the Viterbi algorithm. Then asymptotic upper bounds on the BEAST decoding complexity for three important ensembles of codes are derived. They verify BEAST's high efficiency compared to other algorithms. For high rates, the new asymptotic bound for the best ensemble is in fact better than previously known bounds.
|
|
| 8. |
- Bocharova, Irina, et al.
(författare)
-
Low state complexity block codes via convolutional codes
- 2004
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 50:9, s. 2022-2030
-
Tidskriftsartikel (refereegranskat)abstract
- A new class of block codes with low state complexity of their conventional trellis representations called double zero-tail terminated convolutional codes (DZT codes) is introduced. It is shown that there exist DZT-codes meeting the Varshamov-Gilbert bound on the minimum distance and having asymptotically optimal state complexity. Two ways of constructing DZT-codes are considered. Examples of DZT-codes meeting a lower bound on the state complexity are given.
|
|
| 9. |
- Bocharova, Irina, et al.
(författare)
-
Searching for binary and nonbinary block and convolutional LDPC codes
- 2016
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 62:1, s. 163-183
-
Tidskriftsartikel (refereegranskat)abstract
- A unified approach to search for and optimize codes determined by their sparse parity-check matrices is presented. Replacing the nonzero elements of a binary parity-check matrix (the base or parent matrix) either by circulants or by companion matrices of elements from a finite field GF(2m), we obtain quasi-cyclic low-density parity-check (LDPC) block codes and binary images of nonbinary LDPC block codes, respectively. By substituting monomials of a formal variable D, we obtain the polynomial description of an LDPC convolutional code. A set of performance measures applicable to different classes of LDPC codes is considered, and a greedy algorithm for code performance optimization is presented. The heart of the new optimization algorithm is a fast procedure for searching for LDPC codes with large girth of their Tanner graphs. For a few classes of LDPC codes, examples of codes combining good error-correcting performance with compact representation are obtained. In particular, we present optimized convolutional LDPC codes and conclude that the LDPC block codes are still superior to their convolutional counterparts if both decoding complexity and coding delay are considered. Moreover, a specific channel model can easily be embedded into the optimization loop. Thereby, the code can be optimized for a specific channel. The efficiency of such an optimization is demonstrated via an example of faster than Nyquist (FTN) signaling using LDPC codes. The FTN strategy combined with a rate R = 1/2 LDPC code of length 64800 optimized for effective data rate R = 3/4 gains more than 0.5 dB compared with the standard LDPC codes of the same rate and length. The obtained gain corresponds to transmission at the capacity of the binary input additive white Gaussian noise channel. In most numerical examples, we consider codes with bidiagonal structure of the parity-check matrix. This restriction preserves low encoding complexity and allows fair comparison with codes selected for - ommunication standards.
|
|
| 10. |
- Bocharova, Irina, et al.
(författare)
-
Searching for voltage graph-based LDPC tailbiting codes with large girth
- 2012
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 58:4, s. 2265-2279
-
Tidskriftsartikel (refereegranskat)abstract
- The relation between parity-check matrices of quasi-cyclic (QC) low-density parity-check (LDPC) codes and biadjacency matrices of bipartite graphs supports searching for powerful LDPC block codes. Using the principle of tailbiting, compact representations of bipartite graphs based on convolutional codes can be found. Bounds on the girth and the minimum distance of LDPC block codes constructed in such a way are discussed. Algorithms for searching iteratively for LDPC block codes with large girth and for determining their minimum distance are presented. Constructions based on all-one matrices, Steiner Triple Systems, and QC block codes are introduced. Finally, new QC regular LDPC block codes with girth up to 24 are given.
|
|
