| 1. |
- Anderson, John B, et al.
(author)
-
On the BCJR algorithm for rate-distortion source coding
- 2007
-
In: IEEE Transactions on Information Theory. - 0018-9448. ; 53:9, s. 3201-3207
-
Journal article (peer-reviewed)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. |
- Bocharova, Irina, et al.
(author)
-
An improved bound on the list error probability and list distance properties
- 2008
-
In: IEEE Transactions on Information Theory. - 0018-9448. ; 54:1, s. 13-32
-
Journal article (peer-reviewed)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.
|
|
| 3. |
- Bocharova, Irina, et al.
(author)
-
BEAST decoding of block codes obtained via convolutional codes
- 2005
-
In: IEEE Transactions on Information Theory. - 0018-9448. ; 51:5, s. 1880-1891
-
Journal article (peer-reviewed)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.
|
|
| 4. |
- Bocharova, Irina, et al.
(author)
-
Trellis complexity of short linear codes
- 2007
-
In: IEEE Transactions on Information Theory. - 0018-9448. ; 53:1, s. 361-368
-
Journal article (peer-reviewed)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
|
|
| 5. |
- He, Ching, et al.
(author)
-
Joint permutor analysis and design for multiple turbo codes
- 2006
-
In: IEEE Transactions on Information Theory. - 0018-9448. ; 52:9, s. 4068-4083
-
Journal article (peer-reviewed)abstract
- In this paper, we study the problem of joint permutor analysis and design for J-dimensional multiple turbo codes with J constituent encoders, J>2. The concept of summary distance is extended to multiple permutors of size N and used as the design metric. Using the sphere-packing concept, we prove that the minimum length-2 summary distance (spread) Dmin,2 is asymptoticly upper-bounded by O(N J-1/J). We also show that the asymptotic minimum length-2L summary distance Dmin,2L for the class of random permutors is lower-bounded by O(NJ-2J-epsi/), where epsi>0 can be arbitrarily small. Then, using the technique of expurgating "bad" symbols, we show that the spread of random permutors can achieve the optimum growth rate, i.e., O(NJ-1/J), and that the asymptotic growth rate of Dmin,2L can also be improved. The minimum length-2 and length-4 summary distances are studied for an important practical class of permutors-linear permutors. We prove that there exist J-dimensional multiple linear permutors with optimal spread Dmin,2 =O(NJ-1J/). Finally, we present several joint permutor construction algorithms applicable to multiple turbo codes of short and medium lengths.
|
|
| 6. |
- Hell, Martin, et al.
(author)
-
Two new attacks on the self-shrinking generator
- 2006
-
In: IEEE Transactions on Information Theory. - 0018-9448. ; 52:8, s. 3837-3843
-
Journal article (peer-reviewed)abstract
- The self-shrinking generator was introduced in 1994. It is based on the idea behind the shrinking generator and despite its simplicity it has remained remarkably resistant to efficient attacks. Several known plaintext attacks have been proposed on the generator, some operating on a short keystream and others requiting a longer sequence to succeed. In this paper, two new attacks on the self-shrinking generator are proposed. The first attack, using a short known keystream, has the same complexity as the BDD-based attack, which is the best previously known attack. However, while the BDD-based attack requires a huge amount of memory, the proposed algorithm uses almost no memory, leaving it as the preferred alternative. The second attack operates on a longer known keystream, exponential in the length of the LFSR. The attack considers one or several segments of keystream bits and guesses that these bits stem from LFSR segments of some size. It is shown that this attack achieves better complexity than any previously known attack.
|
|
| 7. |
- Jimenez Feltström, Alberto, et al.
(author)
-
Braided Block Codes
- 2009
-
In: IEEE Transactions on Information Theory. - 0018-9448. ; 55:6, s. 2640-2658
-
Journal article (peer-reviewed)abstract
- A new class of binary iteratively decodable codes with good decoding performance is presented. These codes, called braided block codes (BBCs), operate on continuous data streams and are constructed by interconnection of two component block codes. BBCs can be considered as convolutional (or sliding) version of either Elias' product codes or expander codes. In this paper, we define BBCs, describe methods of their construction, analyze code properties, and study asymptotic iterative decoding performance.
|
|
| 8. |
- Johansson, Thomas, et al.
(author)
-
A linear distinguishing attack on SCREAM
- 2007
-
In: IEEE Transactions on Information Theory. - 0018-9448. ; 53:9, s. 3127-3144
-
Journal article (peer-reviewed)abstract
- A linear distinguishing attack on the stream cipher Scream is proposed. When the keystream is of length 2(98) words, the distinguisher has a detectable advantage. When the keystream length is around 2(120) the advantage is very close to 1. This shows certain weaknesses of Scream. In the process, the paper introduces new general ideas on how to improve the performance of linear distinguishing attacks on stream ciphers.
|
|
| 9. |
- Lentmaier, Michael, et al.
(author)
-
An analysis of the block error probability performance of iterative decoding
- 2005
-
In: IEEE Transactions on Information Theory. - 0018-9448. ; 51:11, s. 3834-3855
-
Journal article (peer-reviewed)abstract
- Asymptotic iterative decoding performance is analyzed for several classes of iteratively decodable codes when the block length of the codes N and the number of iterations I go to infinity. Three classes of codes are considered. These are Gallager's regular low-density parity-check (LDPC) codes, Tanner's generalized LDPC (GLDPC) codes, and the turbo codes due to Berrou et al. It is proved that there exist codes in these classes and iterative decoding algorithms for these codes for which not only the bit error probability Pb, but also the block (frame) error probability PB, goes to zero as N and I go to infinity.
|
|
| 10. |
- Loncar, Maja, et al.
(author)
-
Soft-output BEAST decoding with application to product Codes
- 2008
-
In: IEEE Transactions on Information Theory. - 0018-9448. ; 54:3, s. 1036-1049
-
Journal article (peer-reviewed)abstract
- A Bidirectional Efficient Algorithm for Searching code Trees (BEAST) is proposed for efficient soft-output decoding of block codes and concatenated block codes. BEAST operates on trees corresponding to the minimal trellis of a block code and finds a list of the most probable codewords. The complexity of the BEAST search is significantly lower than the complexity of trellis-based algorithms, such as the Viterbi algorithm and its list-generalizations. The outputs of BEAST, a list of best codewords and their metrics, are used to obtain approximate a posteriori reliabilities of the transmitted symbols, yielding a soft-input soft-output (SISO) symbol decoder referred to as the BEAST-APP decoder. This decoder is employed as a component decoder in iterative schemes for decoding of product and incomplete product codes. Its performance and convergence behavior are investigated using EXIT charts and compared to existing decoding schemes. It is shown that the BEAST-APP decoder achieves performances close to the BCJR decoder with a substantially lower computational complexity.
|
|
