Search

The main aim of this paper is to study various properties of extended binary Golay [24, 12, 8] code, when we know its generator matrix. Using MATLAB, we can study syndrome decoding, weight of a codeword, error correction and error detection of extended binary Golay [24, 12, 8] code.

The main aim of this paper is to study the encoding process of binary Schubert code [43,7] using MATLAB, when one knows its generator matrix. Using MATLAB, we can study syndrome decoding, weight of a codeword, error correction and error detection of the code.

The main aim of this paper is to study various properties of extended binary Hamming [8, 4, 4] code, when we know its generator matrix. Using MATLAB, we can study syndrome decoding, weight of a codeword, error correction and error detection of binary Hamming [8, 4, 4] code.

Code-based public key cryptosystems have been found to be an interesting option in the area of Post-Quantum Cryptography. In this work, we present a key encapsulation mechanism (KEM) using a parity check matrix of the Generalized Srivastava code as the public key matrix. Generalized Srivastava codes are privileged with the decoding technique of Alternant codes as they belong to the family of Alternant codes. We exploit the dyadic structure of the parity check matrix to reduce the storage of the public key. Our encapsulation leads to a shorter ciphertext as compared to DAGS proposed by Banegas et al. in Journal of Mathematical Cryptology which also uses Generalized Srivastava code. Our KEM provides IND-CCA security in the random oracle model. Also, our scheme can be shown to achieve post-quantum security in the quantum random oracle model.

In this chapter, we will explain the construction of linear block codes. Since linear block codes are vector subspaces, we advise to the reader to study Chap. 1 before proceeding to Chap. 2. Without the knowledge of basic concepts of linear algebra, such as groups, fields, vector spaces, and subspaces, it is difficult to comprehend the philosophy behind the concept of linear block codes. We advise the reader to study the section related to the philosophy of channel encoding before studying the sections related to the encoding and decoding operations. We explain the purpose of channel encoding in Sect. 2.5. After introducing the construction of linear block codes, we explain the encoding operation and give some fundamental definitions such as minimum distance, generator matrix, and parity check matrix. In sequel, we explain equivalent codes, error detection and correction capability of linear block codes, and Hamming spheres.

In this chapter, we will first explain the decoding of linear block codes using syndrome tables, then provide information about some well-known preliminary binary linear block codes. Syndrome decoding is a preliminary decoding approach; most of the modern decoding techniques do not employ syndrome decoding. However, to comprehend the decoding logic of linear block codes, it is essential to understand the syndrome decoding operation. For this purpose, we first explain the construction of standard arrays and decoding operation using standard arrays. Syndromes are nothing but concise representation of standard arrays. After standard arrays, we explain the syndrome decoding concept. Following the explanation of the syndrome decoding, we introduce some linear block codes well-known in the literature, such as Golay code, Reed-Muller codes, and Hamming codes, and discuss the error correction capability and decoding operations of these linear block codes. Non-systematic forms of the generator and parity check matrices of the Hamming codes are also explained.

Linear error-block codes were introduced in 2006 as a generalization of linear block codes. In this paper we construct two new families of perfect binary linear error-block codes of \( \pi \)-distance 3, namely, \([n_1]\ldots [n_t][2]^s\) (where \( t\ge 1 \)), and \([n_1][n_t][3]^s\) (where \( t= 1\) or \(t=2\)), we also introduce the notions of Hamming and Simplex linear error-block codes, and we give a method to construct Hamming LEB codes from its parity check matrix. We also prove that Hamming LEB codes are perfect, and the constructed perfect codes are Hamming.

Quasi-cyclic (QC) LDPC codes whose parity-check matrices have diagonal structure play an important role in channel coding of 5G communications. In this paper, we study an algebraic-based method for constructing QC LDPC codes with diagonal structure of parity-check matrices. We first analyze the cycle structure of this class of QC LDPC codes and then divide the diagonal parity-check matrix into two parts, i.e., the diagonal matrix and the non-diagonal matrix. By employing the masking technique, we design the non-diagonal matrix based on prime field and QC LDPC codes with diagonal structure of parity-check matrices are proposed. Numerical results show that the constructed QC LDPC codes perform much better than the WiMAX-LDPC codes.

We present a probabilistic model counter that can trade off running time with approximation accuracy. As in several previous works, the number of models of a formula is estimated by adding random parity constraints (equations). One key difference with prior works is that the systems of parity equations used correspond to the parity check matrices of Low Density Parity Check (LDPC) error-correcting codes. As a result, the equations tend to be much shorter, often containing fewer than 10 variables each, making the search for models that also satisfy the parity constraints far more tractable. The price paid for computational tractability is that the statistical properties of the basic estimator are not as good as when longer constraints are used. We show how one can deal with this issue and derive rigorous approximation guarantees by performing more solver invocations.

Many information sources are naturally analogue and must be digitised if they are to be transmitted digitally. The process of digitisation introduces quantisation errors and increases the bandwidth required. The use of analogue error-correcting codes eliminates the need for digitisation. It is shown that analogue BCH codes may be constructed in the same way as finite-field BCH codes, including Reed–Solomon codes, except that the field of complex numbers is used. It is shown how the Mattson–Solomon polynomial or equivalently the Discrete Fourier transform may be used as the basis for the construction of analogue BCH codes. It is also shown that a permuted parity check matrix produces an equivalent code, using a primitive root of unity to construct the code, as in discrete BCH codes. A new algorithm is presented which uses symbolwise multiplication of rows of a parity check matrix to produce directly the parity check matrix in reduced echelon form. The algorithm may be used for constructing reduced echelon parity check matrices for standard BCH and RS codes as well as analogue BCH codes. Gaussian elimination or other means of solving parallel, simultaneous equations are completely avoided by the method. It is also proven that analogue BCH codes are Maximum Distance Separable (MDS) codes. Examples are presented of using the analogue BCH codes in providing error-correction for analogue, band-limited data including the correction of impulse noise errors in BCH encoded, analogue stereo music waveforms. Since the data is bandlimited it is already redundant and the parity check symbols replace existing values so that there is no need for bandwidth expansion as in traditional error-correcting codes. Future research areas are outlined including the possibility of an analogue, maximum likelihood, error-correcting decoder based on the extended Dorsch decoder of Chap. 15. Steganography is another future application area for analogue BCH codes.

In this paper we consider an error-detecting code based on linear quasigroups. We give a proof that the code is linear. Also, we obtain the generator and the parity-check matrices of the code, from where we obtain the Hamming distance of the code when a linear quasigroup of order 4 from the best class of quasigroups of order 4 for coding, i.e., the class of quasigroups of order 4 that gives smallest probability of undetected errors is used for coding. With this we determine the number of errors that the code will detect for sure.

International audience; Most of the works concerning cryptographic applications of cellular automata (CA) focus on the analysis of the underlying local rules, interpreted as boolean functions. In this paper, we investigate the cryptographic criteria of CA global rules by considering them as vectorial boolean functions. In particular, we prove that the 1-resiliency property of CA with bipermutive local rules is preserved on the corresponding global rules. We then unfold an interesting connection between linear codes and cellular automata, observing that the generator and parity check matrices of cyclic codes correspond to the transition matrices of linear CA. Consequently, syndrome computation in cyclic codes can be performed in parallel by evolving a suitable linear CA, and the error-correction capability is determined by the resiliency of the global rule. As an example, we finally show how to implement the (7, 4, 3) cyclic Hamming code using a CA of radius r=2.

This paper presents a cryptanalysis of a modified version of the Sidelnikov cryptosystem which is based on Reed-Muller codes. This modified scheme consists in inserting random columns in the secret generating matrix or parity check matrix. The cryptanalysis relies on the computation of the squares of the public code. The particular nature of Reed-Muller which are defined by means of multivariate binary polynomials, permits to predicate the value of dimension of the square codes and then to fully recover in polynomial time the secret positions of the random columns. Our work shows that the insertion of random columns in the Sidelnikov scheme does not bring any security improvement.

The syndrome former sub-matrix is introduced. The generator matrix of a convolutional code can be constructed by means of a procedure called null ex-OR sum of clusters of syndromes. Inversely, it is possible to operate by means of the column construction of the parity check matrix. The importance of a parity check matrix in minimal form is stressed. A strict-sense time-invariant convolutional code in its parity check matrix is characterized by a unique interleaved parity check polynomial. It is possible to distinguish between low-rate and high-rate convolutional codes, taking into account their parity check matrix. The dual of a low-rate convolutional code is a high-rate convolutional code, but the outermost parts of the frame show different structures in the two matrices. A systematic encoder circuit based on the unique interleaved parity check polynomial is presented. Traditional encoder circuits for convolutional codes described by means of the parity check matrix are discussed, considering a unique shift register in observer arrangement. Not well designed convolutional codes and the presence of periodic rows in their parity check matrix are studied. The tail-biting arrangement of a convolutional code is revisited looking at its parity check matrix. When the code is not well-designed, the tail-biting convolutional code has a generator matrix not of full rank, and its periodic row in the parity check matrix vanishes. A second conceptual bridge between cyclic block codes and convolutional codes is presented, now based on the parity check matrix. Modified lengthening in the generator matrix and H-extension in the parity check matrix support this correspondence. A family tree for many classes of error correcting codes is depicted. Not well-designed convolutional codes can be considered the dual with respect to convolutional codes whose parity check matrix is not in its minimal form.

A wide-sense time-invariant block code in its parity check matrix exhibits more than one parity check polynomial periodically repeating. Quasi-cyclic codes are revisited from this point of view. Reordered forms of quasi-cyclic codes are treated. Shortening or lengthening, with respect to the quasi-cyclic condition, are possible here only with steps of integer periods. The concept of code duality is extended. Code puncturation is described for quasi-cyclic codes. Constant-length shortening and constant-length puncturation are dual operations by which an information symbol is transformed into a control symbols and vice versa. Modified lengthening and modified H-extension are discussed also for quasi-cyclic codes. Encoder circuits, state diagrams and trellises are finally outlined.

A wide-sense time-invariant convolutional code is characterized by more than one interleaved generator polynomial periodically repeating in its generator matrix. The existence of a right-inverse matrix is to be tested here. The encoder circuit is based on more than one shift register in controller arrangement, or in observer arrangement. A recursive systematic solution is possible, and can be calculated by means of the Smith form of the generator matrix. An equivalence between modified lengthened quasi-cyclic codes and a certain class of w.s. time-invariant convolutional codes is demonstrated. The concept of not well-designed convolutional codes is extended to such codes. Their tail-biting version has analogous characteristics as that introduced for s.s. time-invariant convolutional codes. A first conceptual bridge between quasi-cyclic codes and this type of convolutional codes is outlined. It is based on unwrapping the reordered version of the quasi-cyclic code. Finally, state diagrams and trellises are described. Here the computational complexity has to be calculated also taking into account the number of branches entering the same node. Truncated circulants are introduced for describing reordered versions of convolutional codes not in tail-biting form. A scheme of doubly convolutional code is described for the case in which two series of distributed control symbols are adopted.

Generalized parity check codes in serial concatenation or in parallelepiped concatenation form composite codes whose properties are similar to those of array codes. These two families of codes are comprehensively named binomial product generator codes (BPG codes). In fact, short low-weight code words in them are constructed as the product of a certain number of binomials. They are good LDPC block codes whose performance can be improved avoiding the occurrence of equalities in their construction parameters. The minimum distance, always even, can be predicted. The study of improper array codes is developed more in detail. Generalized array codes, which are still quasi-cyclic, but non-uniform, are analyzed. Their generator matrix, formed by time-varying circulants, is calculated. One further possible variant of improper array codes is presented. A particular class of high-rate quasi-cyclic codes, whose parity check matrix is made by only one layer of circulants, are studied. Their minimum distance is calculated. This class of codes can be transformed, by proper unwrapping, into good high-rate convolutional codes, whose performance can be easily predicted.

A linear transformation of a vector is firstly introduced. A linear code, described by means of its generator matrix, turns us to be a generalization of this concept. The right-inverse of such matrix is associated to the inverse vector transformation. The polynomial description of a linear block code is given adopting a proper generator polynomial, factor of a certain binomial. This unique polynomial is the element shifting in the rows of the generator matrix of a strict-sense time-invariant code described in this way. Code shortening, code punctuation, the concatenation of more than one code are discussed. The concept of subcode is introduced. In this framework code extension appears as a particular form of direct serial code concatenation. The class of cyclic codes is widely investigated, starting from the factorization of any type of binomials in a binary field. Many families of cyclic codes are presented. The structure of BCH codes and their design procedure are analysed. The encoder circuits able to construct any type of polynomial code exhibit evolutions which can be displayed in a suitable state diagram. It is useful to distinguish between systematic and nonsystematic encoders. The main properties of a polynomial code are evidenced in its state diagram. Direct product codes are described. Their generator matrix is calculated. Expressions for the minimum distance and the numbers of low-weight code words are derived. Lengthened cyclic codes and modified lengthened cyclic codes are treated, the latter representing a first step towards the concept of convolutional codes. Generalized parity check codes are discussed together with lengthened cyclic codes. Direct product codes are interpreted as a particular class of modified lengthened codes. The above topics are extended to the case of non-binary fields. We can have here cyclic or, more in general, pseudo-cyclic codes. Minimum-distance-separable codes, and in particular Reed-Solomon codes, are described. Finally a generator trellis, representing the temporal evolution of the state diagram, is constructed. The number of states in its stages gives a measure of the decoding computational complexity in a soft-decision decoding algorithm.

A wide-sense time-invariant block code is characterized by more than one generator polynomial periodically repeating in its generator matrix. Interleaved multiplication enables us to construct a code word. A quasi-cyclic code can be considered as a generalization of a cyclic code, with a characteristic block length, always integer multiple of the period. These codes are presented in a reordered form, traditionally adopted. An interpretation of known block codes with composite block length as quasi-cyclic codes is provided. They can be set in correspondence with cyclic or pseudo-cyclic codes in a non-binary alphabet. Encoder circuits for quasi-cyclic codes are discussed, always adopting the generator matrix model. Their evolution is described in a non-binary state diagram. Also for quasi-cyclic codes, the operations of code shortening, code puncturation, and code lengthening are possible, with reference to either the original form or a properly reordered form. A first introduction to array codes is given. Permutation circulants are adopted as very efficient tools for performing an interleaver function. Modified lengthened quasi-cyclic codes show the typical characteristics of wide-sense time-invariant convolutional codes. The concept of subcodes is extended to the case of quasi-cyclic codes. Finally, some trellises of quasi-cyclic codes are discussed, especially when they allow a simplified computational complexity in soft-decision decoding through a proper partitioning.

The best results on LDPC convolutional codes are summarized. Such results have been obtained, up to now, after proper transformations of good LDPC block codes. Unwrapping assures better performance with respect to that of the original parent block code. Irregular codes appear to be preferable. Modified H-extension offers good possibilities starting from BPG block codes. Nevertheless the parity check constraint length is extremely high. The direct design of LDPC convolutional codes with very short constraint length is outlined, starting from the case of code rate 1/2. A parity check matrix not in minimal form is typically employed, especially when the code is regular. Irregular codes allow to obtain good performance with shorter constraint lengths. The case of high-rate convolutional code is treated deriving their properties from those of 1/2-rate codes. Low-rate convolutional codes require a more involved treatment, since some vertical separations between 1-symbols in their syndrome former sub-matrix can be reused. The case of period length and number of information symbols per period not co-prime is analyzed. Some interesting 2/4-rate codes are presented. Regular and irregular codes are compared, fixing the code rate and minimum distance, in search for the minimum parity check constraint length. Hints for a direct design of LDPC convolutional codes with short constraint length are given. The concept of doubly convolutional codes is revisited.

The parity check matrix can be assumed for an alternative description of a linear code. The relationship with the generator matrix is not univocal, except when such matrices are systematic. Upper triangular generator matrices and lower triangular parity check matrices are presented, showing the advantage of a clear recognition of information and control symbol positions. Error correction is outlined by means of properly processing single-error syndromes. A strict-sense time-invariant code in its parity check matrix is characterized by a unique parity check polynomial. The concept of dual code is discussed. Code puncturation and code shortening are interpreted as dual operations. Constant-length puncturation and constant-length shortening are described. Periodic parity check polynomials in lengthened cyclic codes are constructed. The parity check matrix of a modified lengthened cyclic code is derived. The difference between periodic and non-periodic parity check rows is stressed. H-extended cyclic codes and modified H-extended cyclic codes are introduced. Generalized repetition codes represent dual codes of generalized parity check codes. The whole family of Hamming codes is constructed by repeated lengthening operations. The whole family of simplex codes is constructed by repeated H-extensions. Direct product codes are described by means of their parity check matrix. An encoder circuit based on the parity check polynomial is depicted. Its state diagram is studied, and the trellis obtained from it is compared with the traditional generator trellis. Finally some considerations about the parity check matrix of nonbinary block codes are developed, with particular attention to their error correction capability.

Turbo-codes and low density parity check codes (LDPC) decoders benefit from parallel hardware architectures to meet the requirements in high data rate of modern applications. However, such architectures suffer from memory conflict problems due to concurrent data accesses. This issue comes from the interleaving law in turbo-like codes and from the parity check matrix in LDPC. Different approaches have been developed: definition of conflict-free data access orders, using dedicated hardware mechanisms to deal with conflicts at runtime, finding conflict free memory mappings at design time (off-chip) or more recently a hybrid strategy that finds conflict free memory mappings on-chip at runtime. In this survey, we propose a comprehensive overview of existing strategies to solve memory access conflict problem.

In this chapter, we recall the main definitions concerning quasi-cyclic codes, which will be used in the remainder of the book. We introduce the class of circulant matrices, and the special class of circulant permutation matrices, together with their isomorphism with polynomials over finite fields. We characterize the generator and parity-check matrices of quasi-cyclic codes, by defining their “blocks circulant” and “circulants block” forms, and show how they translate into an encoding circuit. We define a special class of quasi-cyclic codes having the parity-check matrix in the form of a single row of circulant blocks, which will be of interest in the following chapters. Finally, we describe how to achieve efficient encoding algorithms based on fast polynomial multiplication and vector-circulant matrix products.

In a number of situations, it is necessary for two agents who may have never communicated in the past to, jointly, create a shared information item which can serve as a basis for subsequent protocols that the agents may wish to execute (e.g., negotiation or encryption protocols). One way to create this shared piece of information is to have the two agents start with one random bit string each and then engage in a protocol that enables them to transform, gradually, bit differences (in their strings) into bit agreements. In a previous work, an efficient protocol was proposed which was based on the use of the Extended Golay error-correcting code in order to locate and “correct” bit differences. In this work we generalize this protocol in order to use any generic error-correcting code and derive theoretical performance bounds on the efficiency, based on the characteristics of the employed code. The proposed generalized protocol is fair, in that the final strings (which have the same bits in the majority of positions) depend on the strings possessed by both agents while each agent contributes to the same degree in the formation of these strings. Finally, the proposed protocol is lightweight (both computationally and with respect to message exchanges) and, thus, can be implemented in embedded systems and resource limited devices.

This chapter provides a brief overview of the basic concepts and definitions concerning Low-Density Parity-Check (LDPC) codes, which will be used in the remainder of the book. The notation concerning LDPC codes which will be used throughout the book is introduced. LDPC encoding and decoding algorithms and their complexity are also discussed.