| 31. |
- 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.
|
|
| 32. |
- 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.
|
|
| 33. |
- 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.
|
|
| 34. |
- 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.
|
|
| 35. |
- 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.
|
|
| 36. |
- 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.
|
|
| 37. |
- Bocharova, Irina, et al.
(författare)
-
Tailbiting codes: Bounds and search results
- 2002
-
Ingår i: IEEE Transactions on Information Theory. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9448. ; 48:1, s. 137-148
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 38. |
- Bocharova, Irina, et al.
(författare)
-
Tailbiting codes obtained via convolutional codes with large active distance-slopes
- 2002
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 48:9, s. 2577-2587
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)abstract
- The slope of the active distances is an important parameter when investigating the error-correcting capability of convolutional codes and the distance behavior of concatenated convolutional codes. The slope of the active distances is equal to the minimum average weight cycle in the state-transition diagram of the encoder. A general upper bound on the slope depending on the free distance of the convolutional code and new upper bounds on the slope of special classes of binary convolutional codes are derived. Moreover, a search technique, resulting in new tables of rate R = 1/2 and rate R = 1/3 convolutional encoders with high memories and large active distance-slopes is presented. Furthermore, we show that convolutional codes with large slopes can be used to obtain new tailbiting block codes with large minimum distances. Tables of rate R = 1/2 and rate R = 1/3 tailbiting codes with larger minimum distances than the best previously known quasi-cyclic codes are given. Two new tailbiting codes also have larger minimum distances than the best previously known binary linear block codes with same size and length. One of them is also superior in terms of minimum distance to any previously known binary nonlinear block code with the same set of parameters.
|
|
| 39. |
- Bocharova, Irina, et al.
(författare)
-
Trellis complexity of short linear codes
- 2007
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 53:1, s. 361-368
-
Tidskriftsartikel (refereegranskat)abstract
- An extended table of Shuurman's bounds on the state complexity of short binary linear codes is presented. Some new lower and upper bounds are obtained. Most of the newly found codes are based on the so-called double zero-tail termination (DZT) construction
|
|
| 40. |
|
|
