Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Convolutional encoding of self-dual codes

G. Solomon

Published Feb 15, 1994• 2 citations
OpenAlex

Abstract

There exist almost complete convolutional encodings of self-dual codes, i.e., block codes of rate 1/2 with weights w, w = 0 mod 4. The codes are of length 8m with the convolutional portion of length 8m-2 and the nonsystematic information of length 4m-1. The last two bits are parity checks on the two (4m-1) length parity sequences. The final information bit complements one of the extended parity sequences of length 4m. Solomon and van Tilborg have developed algorithms to generate these for the Quadratic Residue (QR) Codes of lengths 48 and beyond. For these codes and reasonable constraint lengths, there are sequential decodings for both hard and soft decisions. There are also possible Viterbi-type decodings that may be simple, as in a convolutional encoding/decoding of the extended Golay Code. In addition, the previously found constraint length K = 9 for the QR (48, 24;12) Code is lowered here to K = 8.

Related papers

Convolutional encoding of self-dual codes

G. Solomon

Self-dual block codes of rate 1/2 are constructed. The codes are of length 8m with weights w, w=0 mod 4. The codes have a convolutional portion of length 8m-2 and non-systematic information length 4m-1. The last two bits are parity checks on the two (4m-1) length parity sequences. The final information bit complements one of the extended parity sequences of length 4m. Solomon and Van Tilborg (1979) have developed algorithms to generate these for the quadratic residue codes of lengths 24 and beyond. For reasonable constraint lengths, there are possible Viterbi type of decodings that may be as simple as in the convolutional encoding/decoding of the extended Golay code. In addition, the K=9 constraint length for the QR (48, 24;12) code found by Solomon and Van Tilborg is lowered to K=8.>

IEEE International Symposium on Information Theory (ISIT)•Dec 17, 2002•2 citations

Convolutional encoding of 60,64,68,72-bit self-dual codes

Zhdanov, Alexander

In this paper we obtain the [60,30,12], [64,32,12], [68,34,12], [72,36,12] self-dual codes as tailbitting convolutional codes with the smallest constraint length K=9. In this construction one information bit is modulo two added to the one of the encoder outputs and the first row in the quasi-cyclic generator matrix is replaced by the obtained row. The pure quasi-cyclic construction with K=10 is also available for [68,34,12] and [72,36,12] codes. The new [72,36,12] singly even self-dual code with parameters Beta=483 Gamma=0 was obtained.

arXiv:1702.05153•Feb 16, 2017•7 citations

Hard- and soft-decision decoding beyond the half minimum distance---An algorithm for linear codes (Corresp.)

Martin Bossert, F. Hergert

A decoding algorithm for linear codes that uses the minimum weight words of the dual code as parity checks is defined. This algorithm is able to correct beyond the half minimum distance and has the capability of including soft-decision decoding. Results on applying this algorithm to quadratic residue (QR) codes, BCH codes, and the Golay codes (with and without soft-decision decoding) are presented.

IEEE Transactions on Information Theory•Sep 1, 1986•39 citations

Two-level decoding of (32, 16, 8) quadratic residue code

Jing Shun Yuan, C.S. Chen, Shang‐Chih Ma

The Pless construction of the (24, 12, 8) extended Golay code can be modified to construct the (32, 16, 8) extended QR code. Some structural similarities are discovered between the (32, 16, 8) QR code and the (24, 12, 8) Golay code. A simple decoder is developed based on the two-level structure of the (32, 16, 8) QR code. In addition to correcting all three or less bit errors, the proposed algorithm is able to correct some four-bit error patterns. Recently, soft-logic decoding of block codes has found increasing practical applications. The two-level structure renders an extension of Vardy and Be‘ery’s fast algorithm to the (32, 16, 8) QR code. The Vardy-Be‘ery’s algorithm is, so far, the most efficient scheme for the Golay code in the literature, with direct application impact. Its extension to the (32, 16, 8) code is also computationally efficient, as analysed in detail.

IEE Proceedings I Communications Speech and Vision•Jan 1, 1993•9 citations

On maximum likelihood soft decoding of some binary self-dual codes

Moshe Ran, Jakov Snyders

Efficient algorithms are derived for maximum likelihood (ML) soft-decision decoding of some binary self-dual codes. A family of easily decodable self-dual codes is derived by modifying a known F/sub 24/, which has a weight distribution resembling that of the (24, 12, 8) Golay code G/sub 24/. The ML decoding of F/sub 24/ is accomplished by only 227 real additions, compared to 651 required for G/sub 24/, yet the error rates of the two decoders are similar for moderate noise conditions.>

IEEE Transactions on Communications•Mar 1, 1993•13 citations

The Art of Error Correcting Coding

Robert H. Morelos-Zaragoza

Preface. Foreword. The ECC web site. 1. Introduction. 1.1 Error correcting coding: Basic concepts. 1.1.1 Block codes and convolutional codes. 1.1.2 Hamming distance, Hamming spheres and error correcting capability. 1.2 Linear block codes. 1.2.1 Generator and parity-check matrices. 1.2.2 The weight is the distance. 1.3 Encoding and decoding of linear block codes. 1.3.1 Encoding with G and H. 1.3.2 Standard array decoding. 1.3.3 Hamming spheres, decoding regions and the standard array. 1.4 Weight distribution and error performance. 1.4.1 Weight distribution and undetected error probability over a BSC. 1.4.2 Performance bounds over BSC, AWGN and fading channels. 1.5 General structure of a hard-decision decoder of linear codes. Problems. 2. Hamming, Golay and Reed-Muller codes. 2.1 Hamming codes. 2.1.1 Encoding and decoding procedures. 2.2 The binary Golay code. 2.2.1 Encoding. 2.2.2 Decoding. 2.2.3 Arithmetic decoding of the extended (24, 12, 8) Golay code. 2.3 Binary Reed-Muller codes. 2.3.1 Boolean polynomials and RM codes. 2.3.2 Finite geometries and majority-logic decoding. Problems. 3. Binary cyclic codes and BCH codes. 3.1 Binary cyclic codes. 3.1.1 Generator and parity-check polynomials. 3.1.2 The generator polynomial. 3.1.3 Encoding and decoding of binary cyclic codes. 3.1.4 The parity-check polynomial. 3.1.5 Shortened cyclic codes and CRC codes. 3.1.6 Fire codes. 3.2 General decoding of cyclic codes. 3.2.1 GF(2m) arithmetic. 3.3 Binary BCH codes. 3.3.1 BCH bound. 3.4 Polynomial codes. 3.5 Decoding of binary BCH codes. 3.5.1 General decoding algorithm for BCH codes. 3.5.2 The Berlekamp-Massey algorithm (BMA). 3.5.3 PGZ decoder. 3.5.4 Euclidean algorithm. 3.5.5 Chien search and error correction. 3.5.6 Errors-and-erasures decoding. 3.6 Weight distribution and performance bounds. 3.6.1 Error performance evaluation. Problems. 4. Nonbinary BCH codes: Reed-Solomon codes. 4.1 RS codes as polynomial codes. 4.2 From binary BCH to RS codes. 4.3 Decoding RS codes. 4.3.1 Remarks on decoding algorithms. 4.3.2 Errors-and-erasures decoding. 4.4 Weight distribution. Problems. 5. Binary convolutional codes. 5.1 Basic structure. 5.1.1 Recursive systematic convolutional codes. 5.1.2 Free distance. 5.2 Connections with block codes. 5.2.1 Zero-tail construction. 5.2.2 Direct-truncation construction. 5.2.3 Tail-biting construction. 5.2.4 Weight distributions. 5.3 Weight enumeration. 5.4 Performance bounds. 5.5 Decoding: Viterbi algorithm with Hamming metrics. 5.5.1 Maximum-likelihood decoding and metrics. 5.5.2 The Viterbi algorithm. 5.5.3 Implementation issues. 5.6 Punctured convolutional codes. 5.6.1 Implementation issues related to punctured convolutional codes. 5.6.2 RCPC codes. Problems. 6. Modifying and combining codes. 6.1 Modifying codes. 6.1.1 Shortening. 6.1.2 Extending. 6.1.3 Puncturing. 6.1.4 Augmenting, expurgating and lengthening. 6.2 Combining codes. 6.2.1 Time sharing of codes. 6.2.2 Direct sums of codes. 6.2.3 The |u|u + v|-construction and related techniques. 6.2.4 Products of codes. 6.2.5 Concatenated codes. 6.2.6 Generalized concatenated codes. 7. Soft-decision decoding. 7.1 Binary transmission over AWGN channels. 7.2 Viterbi algorithm with Euclidean metric. 7.3 Decoding binary linear block codes with a trellis. 7.4 The Chase algorithm. 7.5 Ordered statistics decoding. 7.6 Generalized minimum distance decoding. 7.6.1 Sufficient conditions for optimality. 7.7 List decoding. 7.8 Soft-output algorithms. 7.8.1 Soft-output Viterbi algorithm. 7.8.2 Maximum-a posteriori (MAP) algorithm. 7.8.3 Log-MAP algorithm. 7.8.4 Max-Log-MAP algorithm. 7.8.5 Soft-output OSD algorithm. Problems. 8. Iteratively decodable codes. 8.1 Iterative decoding. 8.2 Product codes. 8.2.1 Parallel concatenation: Turbo codes. 8.2.2 Serial concatenation. 8.2.3 Block product codes. 8.3 Low-density parity-check codes. 8.3.1 Tanner graphs. 8.3.2 Iterative hard-decision decoding: The bit-flip algorithm. 8.3.3 Iterative probabilistic decoding: Belief propagation. Problems. 9. Combining codes and digital modulation. 9.1 Motivation. 9.1.1 Examples of signal sets. 9.1.2 Coded modulation. 9.1.3 Distance considerations. 9.2 Trellis-coded modulation (TCM). 9.2.1 Set partitioning and trellis mapping. 9.2.2 Maximum-likelihood. 9.2.3 Distance considerations and error performance. 9.2.4 Pragmatic TCM and two-stage decoding. 9.3 Multilevel coded modulation. 9.3.1 Constructions and multistage decoding. 9.3.2 Unequal error protection with MCM. 9.4 Bit-interleaved coded modulation. 9.4.1 Gray mapping. 9.4.2 Metric generation: De-mapping. 9.4.3 Interleaving. 9.5 Turbo trellis-coded modulation. 9.5.1 Pragmatic turbo TCM. 9.5.2 Turbo TCM with symbol interleaving. 9.5.3 Turbo TCM with bit interleaving. Problems. Appendix A: Weight distributions of extended BCH codes. A.1 Length 8. A.2 Length 16. A.3 Length 32. A.4 Length 64. A.5 Length 128. Bibliography. Index.

Wiley eBooks•Mar 11, 2002•377 citations
There exist almost complete convolutional encodings of self-dual codes, i.e., block codes of rate 1/2 with weights w, w = 0 mod 4. The codes are of length 8m with the convolutional portion of length 8m-2 and the nonsystematic information of length 4m-1. The last two bits are parity checks on the two (4m-1) length parity sequences. The final information bit complements one of the extended parity sequences of length 4m. Solomon and van Tilborg have developed algorithms to generate these for the Quadratic Residue (QR) Codes of lengths 48 and beyond. For these codes and reasonable constraint lengths, there are sequential decodings for both hard and soft decisions. There are also possible Viterbi-type decodings that may be simple, as in a convolutional encoding/decoding of the extended Golay Code. In addition, the previously found constraint length K = 9 for the QR (48, 24;12) Code is lowered here to K = 8.
Self-dual block codes of rate 1/2 are constructed. The codes are of length 8m with weights w, w=0 mod 4. The codes have a convolutional portion of length 8m-2 and non-systematic information length 4m-1. The last two bits are parity checks on the two (4m-1) length parity sequences. The final information bit complements one of the extended parity sequences of length 4m. Solomon and Van Tilborg (1979) have developed algorithms to generate these for the quadratic residue codes of lengths 24 and beyond. For reasonable constraint lengths, there are possible Viterbi type of decodings that may be as simple as in the convolutional encoding/decoding of the extended Golay code. In addition, the K=9 constraint length for the QR (48, 24;12) code found by Solomon and Van Tilborg is lowered to K=8.>
In this paper we obtain the [60,30,12], [64,32,12], [68,34,12], [72,36,12] self-dual codes as tailbitting convolutional codes with the smallest constraint length K=9. In this construction one information bit is modulo two added to the one of the encoder outputs and the first row in the quasi-cyclic generator matrix is replaced by the obtained row. The pure quasi-cyclic construction with K=10 is also available for [68,34,12] and [72,36,12] codes. The new [72,36,12] singly even self-dual code with parameters Beta=483 Gamma=0 was obtained.
The Pless construction of the (24, 12, 8) extended Golay code can be modified to construct the (32, 16, 8) extended QR code. Some structural similarities are discovered between the (32, 16, 8) QR code and the (24, 12, 8) Golay code. A simple decoder is developed based on the two-level structure of the (32, 16, 8) QR code. In addition to correcting all three or less bit errors, the proposed algorithm is able to correct some four-bit error patterns. Recently, soft-logic decoding of block codes has found increasing practical applications. The two-level structure renders an extension of Vardy and Be‘ery’s fast algorithm to the (32, 16, 8) QR code. The Vardy-Be‘ery’s algorithm is, so far, the most efficient scheme for the Golay code in the literature, with direct application impact. Its extension to the (32, 16, 8) code is also computationally efficient, as analysed in detail.
Preface. Foreword. The ECC web site. 1. Introduction. 1.1 Error correcting coding: Basic concepts. 1.1.1 Block codes and convolutional codes. 1.1.2 Hamming distance, Hamming spheres and error correcting capability. 1.2 Linear block codes. 1.2.1 Generator and parity-check matrices. 1.2.2 The weight is the distance. 1.3 Encoding and decoding of linear block codes. 1.3.1 Encoding with G and H. 1.3.2 Standard array decoding. 1.3.3 Hamming spheres, decoding regions and the standard array. 1.4 Weight distribution and error performance. 1.4.1 Weight distribution and undetected error probability over a BSC. 1.4.2 Performance bounds over BSC, AWGN and fading channels. 1.5 General structure of a hard-decision decoder of linear codes. Problems. 2. Hamming, Golay and Reed-Muller codes. 2.1 Hamming codes. 2.1.1 Encoding and decoding procedures. 2.2 The binary Golay code. 2.2.1 Encoding. 2.2.2 Decoding. 2.2.3 Arithmetic decoding of the extended (24, 12, 8) Golay code. 2.3 Binary Reed-Muller codes. 2.3.1 Boolean polynomials and RM codes. 2.3.2 Finite geometries and majority-logic decoding. Problems. 3. Binary cyclic codes and BCH codes. 3.1 Binary cyclic codes. 3.1.1 Generator and parity-check polynomials. 3.1.2 The generator polynomial. 3.1.3 Encoding and decoding of binary cyclic codes. 3.1.4 The parity-check polynomial. 3.1.5 Shortened cyclic codes and CRC codes. 3.1.6 Fire codes. 3.2 General decoding of cyclic codes. 3.2.1 GF(2m) arithmetic. 3.3 Binary BCH codes. 3.3.1 BCH bound. 3.4 Polynomial codes. 3.5 Decoding of binary BCH codes. 3.5.1 General decoding algorithm for BCH codes. 3.5.2 The Berlekamp-Massey algorithm (BMA). 3.5.3 PGZ decoder. 3.5.4 Euclidean algorithm. 3.5.5 Chien search and error correction. 3.5.6 Errors-and-erasures decoding. 3.6 Weight distribution and performance bounds. 3.6.1 Error performance evaluation. Problems. 4. Nonbinary BCH codes: Reed-Solomon codes. 4.1 RS codes as polynomial codes. 4.2 From binary BCH to RS codes. 4.3 Decoding RS codes. 4.3.1 Remarks on decoding algorithms. 4.3.2 Errors-and-erasures decoding. 4.4 Weight distribution. Problems. 5. Binary convolutional codes. 5.1 Basic structure. 5.1.1 Recursive systematic convolutional codes. 5.1.2 Free distance. 5.2 Connections with block codes. 5.2.1 Zero-tail construction. 5.2.2 Direct-truncation construction. 5.2.3 Tail-biting construction. 5.2.4 Weight distributions. 5.3 Weight enumeration. 5.4 Performance bounds. 5.5 Decoding: Viterbi algorithm with Hamming metrics. 5.5.1 Maximum-likelihood decoding and metrics. 5.5.2 The Viterbi algorithm. 5.5.3 Implementation issues. 5.6 Punctured convolutional codes. 5.6.1 Implementation issues related to punctured convolutional codes. 5.6.2 RCPC codes. Problems. 6. Modifying and combining codes. 6.1 Modifying codes. 6.1.1 Shortening. 6.1.2 Extending. 6.1.3 Puncturing. 6.1.4 Augmenting, expurgating and lengthening. 6.2 Combining codes. 6.2.1 Time sharing of codes. 6.2.2 Direct sums of codes. 6.2.3 The |u|u + v|-construction and related techniques. 6.2.4 Products of codes. 6.2.5 Concatenated codes. 6.2.6 Generalized concatenated codes. 7. Soft-decision decoding. 7.1 Binary transmission over AWGN channels. 7.2 Viterbi algorithm with Euclidean metric. 7.3 Decoding binary linear block codes with a trellis. 7.4 The Chase algorithm. 7.5 Ordered statistics decoding. 7.6 Generalized minimum distance decoding. 7.6.1 Sufficient conditions for optimality. 7.7 List decoding. 7.8 Soft-output algorithms. 7.8.1 Soft-output Viterbi algorithm. 7.8.2 Maximum-a posteriori (MAP) algorithm. 7.8.3 Log-MAP algorithm. 7.8.4 Max-Log-MAP algorithm. 7.8.5 Soft-output OSD algorithm. Problems. 8. Iteratively decodable codes. 8.1 Iterative decoding. 8.2 Product codes. 8.2.1 Parallel concatenation: Turbo codes. 8.2.2 Serial concatenation. 8.2.3 Block product codes. 8.3 Low-density parity-check codes. 8.3.1 Tanner graphs. 8.3.2 Iterative hard-decision decoding: The bit-flip algorithm. 8.3.3 Iterative probabilistic decoding: Belief propagation. Problems. 9. Combining codes and digital modulation. 9.1 Motivation. 9.1.1 Examples of signal sets. 9.1.2 Coded modulation. 9.1.3 Distance considerations. 9.2 Trellis-coded modulation (TCM). 9.2.1 Set partitioning and trellis mapping. 9.2.2 Maximum-likelihood. 9.2.3 Distance considerations and error performance. 9.2.4 Pragmatic TCM and two-stage decoding. 9.3 Multilevel coded modulation. 9.3.1 Constructions and multistage decoding. 9.3.2 Unequal error protection with MCM. 9.4 Bit-interleaved coded modulation. 9.4.1 Gray mapping. 9.4.2 Metric generation: De-mapping. 9.4.3 Interleaving. 9.5 Turbo trellis-coded modulation. 9.5.1 Pragmatic turbo TCM. 9.5.2 Turbo TCM with symbol interleaving. 9.5.3 Turbo TCM with bit interleaving. Problems. Appendix A: Weight distributions of extended BCH codes. A.1 Length 8. A.2 Length 16. A.3 Length 32. A.4 Length 64. A.5 Length 128. Bibliography. Index.