Search

In his pioneering work on LDPC codes, Gallager dismissed codes with parity-check matrices of weight two after proving that their minimum Hamming distances grow at most logarithmically with their code lengths. In spite of their poor minimum Hamming distances, it is shown that quasi-cyclic LDPC codes with parity-check matrices of column weight two have good capability to correct phased bursts of erasures which may not be surpassed by using quasi-cyclic LDPC codes with parity-check matrices of column weight three or more. By modifying the parity-check matrices of column weight two and globally coupling them, the erasure correcting capability can be further enhanced. Quasi-cyclic LDPC codes with parity-check matrices of column weight three or more that can correct phased bursts of erasures and perform well over the AWGN channel are also considered. Examples of such codes based on Reed-Solomon and Gabidulin codes are presented.

In this paper we prove new lower bounds for the maximal size of permutation codes by connecting the theory of permutation codes with the theory of linear block codes. More specifically, using the columns of a parity check matrix of an $[n,k,d]_q$ linear block code, we are able to prove the existence of a permutation code in the symmetric group of degree $n$, having minimum distance at least $d$ and large cardinality. With our technique, we obtain new lower bounds for permutation codes that enhance the ones in the literature and provide asymptotic improvements in certain regimes of length and distance of the permutation code., Comment: 12 pages

The manuscript presents the construction of a diagonally structured Parity check matrix using lower and upper (LU) decomposition for regular Quasi Cyclic-Low Density Parity Check Codes (QC-LDPC) with girth 12. This diagonally structured parity check matrix reduces the sparsity characteristics of QC-LDPC codes. The regular Quasi Cyclic-LDPC code has been constructed using circulant shifting and randomization method in which uniform distribution of non-zero elements, XOR operation, and pairing of row and column has been done. A Simplified Log Domain Sum-Product Algorithm (SLDSPA) is used for the decoding of the constructed code. To reduce the CPU run time of the constructed code, a column-wise loop optimization technique is applied. The frame error rate and CPU run time is calculated for different code lengths such as code1 (816, 408), code2 (1008, 504), code3 (1032, 516), code4 (1944, 972), code5 (672, 336) and code6 (504, 252). The construction of regular QC-LDPC codes on half code rate is obtained for the weight of each row is 6 and each column is given by 3. The results showing that the constructed code is better performing in terms of Low FER (10−1 to 10−7), Low SNR (0 to 3.5 dB) and Less CPU run time in milliseconds.

We provide a procedure to construct entanglement-assisted Calderbank–Shor–Steane (CSS) codes over qudits from the parity check matrices of two classical codes over $\mathbb {F}_q$ , where $q=p^k$ , $p$ is prime, and $k$ is a positive integer. The construction procedure involves the proposed Euclidean Gram–Schmidt orthogonalization algorithm, followed by a procedure to extend the quantum operators to obtain stabilizers of the code. Using this construction, we provide a construction of entanglement-assisted tensor product codes from classical tensor product codes over $\mathbb {F}_q$ . We further show that a nonzero rate entanglement-assisted tensor product code can be obtained from a classical tensor product code whose component codes yield zero rate entanglement-assisted CSS codes. We view this result as the coding analog of superadditivity.

In this letter, sufficient conditions for the determination of the girth are studied from the perspective of matroid theory. The girth of a Tanner graph is at least $2(t_{1}+2)$ if $t_{1}$ specific conditions are simultaneously met. A novel method of constructing high-rate low-density parity-check (LDPC) codes is proposed based on the matroid theory. The parity-check matrices of the constructed LDPC codes are in the form of H = [I $\vert$ H2] with H2 constructed under the conditions of a given girth and a fixed column weight (e.g., $W_{c}=4$ or $W_{c}=6$ ). Simulation results verify that the proposed LDPC codes outperform those in the literature over additive white Gaussian noise channels in terms of bit error rate performance.

This research was funded by AEI (https://doi.org/10.13039/501100011033 (accessed on 6 August 2021)), grant number PID2019-110525GB-I00., We design a decoding algorithm for linear codes over finite chain rings given by their parity check matrices. It is assumed that decoding algorithms over the residue field are known at each degree of the adic decomposition., PID2019-110525GB-I00

This work proposes a new code which can be considered as the modification of linear block code with code rate 1/2 and less than 1/2. The theme of the work is derived from the controllability of discrete time system and accordingly the generator matrix is chosen. A procedure is proposed in this paper which can transform the lower dimensional space to higher dimensional space. A Code is subspace of a space, so, with the help of addition of an equivalent identity matrix, between I (Identity matrix) and P (Parity Check) matrix of the established generator matrix, the lower dimensional space is transformed to higher dimensional space. Multiple numbers of errors could be corrected with the help of this designed code. It is also shown that decoding of this code can be established using the methods like syndrome detection and nearest neighbor decoding. The proposed code satisfies all the bounds. The minimum distance d, which could be achieved here, is at least equal to the total no. of information bits wh...

An algorithm for constructing parity-check matrices of non-binary quasi-cyclic low-density parity-check (NB QC-LDPC) codes is proposed. The algorithm finds short cycles in the base matrix and tries to eliminate them by selecting the circulants and the elements of GF(q). The algorithm tries to eliminate the cycles with the smallest number edges going outside the cycle. The efficiency of the algorithm is demonstrated by means of simulations. In order to explain the simulation results we also derive upper bounds on the minimum distance of NB QC-LDPC codes.

In this paper we address the problem of list decoding of linear codes over an integer residue ring Zq, where qis a power of a prime p. The proposed procedure exploits a particular matrix representation of the linear code over Zpr, called the standard form, and the p-adic expansion of the to-be-decoded vector. In particular, we focus on the erasure channel in which the location of the errors is known. This problem then boils down to solving a system of linear equations with coefficients in Zpr. From the parity-check matrix representations of the code we recursively select certain equations that a codeword must satisfy and have coefficients only in the field pr−1Zpr. This yields a step by step procedure obtaining a list of the closest codewords to a given received vector with some of its coordinates erased. We show that such an algorithm actually computes all possible erased coordinates, that is, the provided list is minimal. This work of the second and forth authors is supported by the Center for Research and Development in Mathematics and Applications (CIDMA) through the Portuguese Foundation for Science and Technology (FCT-Fundação para a Ciência e a Tecnologia), references UIDB/04106/2020 and UIDP/04106/2020. The first author partially supported by Ministerio de Ciencia e Innovación via the grant with ref. PID2019-108668GB-I00. The third author is supported by the Swiss Confederation through the Swiss Government Excellence Scholarship no: 2019.0413 and by the Swiss National Science Foundation grant n. 188430.

The notion of Generalized Hamming weights of block codes has been investigated since the nineties due to its significant role in coding theory and cryptography. In this paper we extend this concept to the context of convolutional codes. In particular, we focus on column distances and introduce the novel notion of generalized column distances (GCD). We first show that the hierarchy of GCD is strictly increasing. We then provide characterizations of such distances in terms of the truncated parity-check matrix of the code, that will allow us to determine their values. Finally, the case in which the parity-check matrix is in systematic form is treated. This work was supported in part by the Sao Paulo Research Foundation (FAPESP) under Grant 2013/25977-7. The work of Sara D. Cardell was supported in part by the FAPESP, under Grant 2015/07246-0 and in part by the CAPES. The work of Marcelo Firer was supported in part by the CNPq. The work of Diego Napp was supported in part by the Spanish, Generalitat Valenciana, Univesitat d’Alacant, under Grant AICO/2017/128 and Grant VIGROB-287.

A famous result of Bonisoli characterizes the equidistant linear codes over $${\mathrm{GF}}(q)$$ (up to monomial equivalence) as replications of some q-ary simplex code, possibly with added 0-coordinates. We first prove a variation of this theorem which characterizes the replications of first order generalized Reed–Muller codes among the two-weight linear codes. In the second part of this paper, we use Bonisoli’s theorem and our variation to study the linear block codes of Steiner triple systems, which can only be non-trivial in the binary and ternary case. Assmus proved that the block by point incidence matrices of all Steiner triple systems on v points which have the same 2-rank generate equivalent binary codes and gave an explicit description of a generator matrix for such a code. We provide an alternative, considerably simpler, proof for these results by constructing parity check matrices for the binary codes spanned by the incidence matrix of a Steiner triple system instead, and we also obtain analogues for the ternary case. Moreover, we give simple alternative coding theoretical proofs for the lower bounds of Doyen, Hubaut and Vandensavel on the 2- and 3-ranks of Steiner triple systems.

In view of the problems that the encoding complexity of quasi-cyclic low-density parity-check (QC-LDPC) codes is high and the minimum distance is not large enough which leads to the degradation of the error-correction performance, the new irregular type-II QC-LDPC codes based on perfect cyclic difference sets (CDSs) are constructed. The parity check matrices of these type-II QC-LDPC codes consist of the zero matrices with weight of 0, the circulant permutation matrices (CPMs) with weight of 1 and the circulant matrices with weight of 2 (W2CMs). The introduction of W2CMs in parity check matrices makes it possible to achieve the larger minimum distance which can improve the error- correction performance of the codes. The Tanner graphs of these codes have no girth-4, thus they have the excellent decoding convergence characteristics. In addition, because the parity check matrices have the quasi-dual diagonal structure, the fast encoding algorithm can reduce the encoding complexity effectively. Simulation results show that the new type-II QC-LDPC codes can achieve a more excellent error-correction performance and have no error floor phenomenon over the additive white Gaussian noise (AWGN) channel with sum-product algorithm (SPA) iterative decoding.

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.

In this paper, we focus on the problem of compressive sensing using binary measurement matrices, and basis pursuit as the recovery algorithm. We obtain new lower bounds on the number of samples to achieve robust sparse recovery using binary matrices and derive sufficient conditions for a binary matrix with fixed column-weight to satisfy the robust null space property. Next we prove that any column-regular binary matrix with girth 6 has nearly optimal number of measurements. Then we show that the parity check matrices of array LDPC codes are nearly optimal in the sense of having girth six and almost satisfying the lower bound on the number of samples. Array code parity check matrices demonstrate an example of binary matrices that achieve guaranteed recovery via robust null-space property and in practice for $n \leq 10^{6}$ provide faster recovery compared to the Gaussian counterpart. This is an extended abstract without proofs. The full paper with additional details can be found in [1].

We investigate how to cancel interference by using space time code and codeword space alignment for multiple-input multiple-output (MIMO) Y channel consisting of three users and a relay. All the nodes adopt Alamouti code. During the multiple access (MA) stage, two codewords within each reciprocal codeword pair are aligned through pre-coding. The relay decodes the elements of each codeword pair using the orthogonal property of effective channel matrix of Alamouti codeword. During the broadcast (BC) stage, the interference between codeword pairs at each user is eliminated by the orthogonal property of effective channel matrix of Alamouti codeword, instead of the interference alignment (IA) pre-coding. Thus, channel state information (CSI) is not required during the BC stage, which greatly reduce the amount of feedback.

A generator matrix (GM)-based approach for adaptively deriving cut-inducing redundant parity checks (RPCs) during the adaptive linear programming decoding algorithm is presented. More precisely speaking, if the decoder gets stuck in a non-integral pseudocodeword, then the resulting RPCs are likely to provide violated forbidden-set inequalities that can separate this non-integral optimal solution from the feasible region. The described approach can be viewed as a GM-based counterpart of the approach proposed by Zhang and Siegel in 2012. For binary linear codes of low rate, while providing the same error-correcting performance, our approach requires much less computational time compared to its analogue.

In this paper, we investigate a codeword refinement technique called double codeword coding in the context of MIMO feedback. In the proposed method, the second codeword is fed back in addition to the best codeword as their interpolation at the transmitter improves the channel knowledge. The derivation of the optimal interpolation parameter is presented together with the derivation of an upper-bound to the interpolation parameter based on channel quality feedback available at the transmitter. We show that double codeword feedback refinement has slightly lower complexity than alternative techniques and still achieves similar performance. Furthermore, double codeword coding can be generalized to higher transmission ranks. Using extended multiuser MIMO link simulations, we verify that the double codeword feedback is able to provide significant gains in 3GPP LTE context.

By using the finite projective geometry method, the separating properties of linear constant-weight codes are presented. An algorithm is given for computing the cardinality of separating coordinate positions of certain disjoint codeword sets of linear constant-weight codes.

A construction method for girth-eight quasi-cyclic low-density parity-check codes (QC-LDPCs) with low encoding complexity is proposed in this study. To avoid short cycles and further improve the performance of the authors proposed codes, the greatest common divisor (GCD)-based method is utilised to construct the information part with girth-eight of the parity-check matrix with systematic form. Furthermore, the quasi-dual-diagonal structure is adopted as the parity part of the parity-check matrix for fast encoding, which not only maintains the parity-check matrix with girth-eight, but also efficiently decreases the encoding complexity of their proposed codes. Simulation results show that their proposed codes perform better than Mackay's codes and the QC-LDPCs constructed by the GCD-based method, and have comparable performance compared with progressive edge growth based QC-LDPCs. Besides, their proposed codes have lower encoding complexity due to the property of fast encoding.

Trapping sets strongly degrade performance of low-density parity check (LDPC) codes in the low-error-rate region. This creates significant difficulties for the deployment of LDPC codes to low-error-rate applications such as storage and wireless systems with no or limited retransmission options. We propose a novel technique for breaking trapping sets based on collaborative decoding that utilizes two different decoding modes. While the main decoding mode executes message passing based on the original parity check matrix of the corresponding LDPC code, the sub-decoding mode operates on a modified parity check matrix formed by removing a portion of check nodes in the factor graph representation of the given code. The modified parity check matrix is designed to promote a passing of correct information into erroneous variable nodes in the trapping set. Theoretical properties of the proposed trapping-set-breaking technique have been established based on the notion of the improved separation for the trapped variable nodes. Simulation results show that the proposed collaborative LDPC decoding scheme switching between the two decoding modes back and forth effectively breaks dominant trapping sets of various known types of regular and irregular LDPC codes.

This paper presents new half rate Quasi Cyclic Low Density Parity Check (QC- LDPC) codes formed on the basis of combinatorial designs. In these codes, circulant matrices of the parity check matrix are formed on the basis of subsets in which the difference between any two elements of a subset is unique with all differences obtained from the same or different subsets. This structure of circulant matrices guarantees non-existence of cycle-4 in the Tanner graph of QC-LDPC codes. First, an irregular code with girth 6 constituted by two rows of circulant matrices is proposed. Then, more criteria will be considered on the structure of subsets with the mentioned feature aiming to represent a new scheme of regular QC-LPDC codes with girth at least 8. From simulations, it is confirmed that codes have similar to or better performance than other well-known half rate codes, while require lower complexity in their design.

A further study of large payloads ME by improving the embedding efficiency is proposed.A new matrix is constructed for ME.A sub-optimal search strategy is exploited to reduce the computational complexity.Effective and practically feasible large payloads ME can be realized by the proposed method. Matrix embedding (ME) is a well-known steganographic method that can improve the embedding efficiency. In ME, the sender and recipient agree in advance on a parity check matrix (PCM) of a binary linear code and utilize the PCM for data embedding. At the decoder side, the embedded message can be extracted by the recipient as the syndrome of the received stego data. The PCM can be taken as any full-ranked matrix and its selection is actually crucial to the embedding performance. In this paper, by extending some previous works, we propose a novel scheme to further improve the embedding efficiency of large payloads ME. First, we utilize a new and specifically designed matrix for ME. Then, instead of finding a coset leader as the modification to the cover which is time consuming, we turn to finding a vector in the coset with relatively small Hamming weight. By the proposed approach, effective and practically feasible large payloads ME can be realized, and extensive experiments show that, a significant increase of embedding efficiency is achieved compared with some state-of-the-art works.

ISC-array LDPC code matrix is evolved from SC-array LDPC code matrix to improve compressive sensing performance for large-size sparse signal. When q is a prime number, no repetitive row occurs in the shift index of SC-array LDPC code matrix, ISC-array LDPC code matrix performs comparably with SC-array LDPC code matrix. When q is a non-prime number, some repetitive rows will appear in the shift index of SC-array LDPC code matrix, which results in more 4-cycles and decreases the compressive sensing performance. ISC-array LDPC code matrix outperforms SC-array LDPC code matrix by effectively reducing or even eliminating the repetitive rows according to their distribution rule, 4-cycles are removed to the maximum extent. ISC-array LDPC code matrix qualifies for compressive sensing because of satisfying RIP well. It also has good quasi-cyclic structure and supports arbitrary code lengths. The simulations verify that the optimised ISC-array LDPC code matrix is advantageous in the image reconstruction quality, the robustness to noise performance and the algorithm complexity.

In this paper, we are interested in finding an algebraic structure of conjucyclic codes of length n over the finite field F 4 . We show that conjucyclic codes of length n over F 4 are related to binary cyclic codes of length 2n and show that there is a canonical bijective correspondence between the two sets. We illustrate how the factorization of the polynomial x 2 n + 1 plays a critical role in each setting. Moreover, we construct the generator and parity check matrices of conjucyclic codes of length n over F 4 .

This paper proposes a new method for building low-density-parity-check codes, exempt of cycle of length 4, based on a circulant permutation matrix, which needs very little memory for storage it in the encoder and a dual diagonal structure is applied to guarantee that parity check bits can be recursively computed with linear calculation complexity. The Bit Error Rate performance of the new low-density-parity-check codes was compared to the uncoded bi-phase-shift-keying over additive-white-gaussian-noise channel. This simulation shows that the proposed codes are very efficient over additive-white-gaussian-noise. The proposed codes ensure a very low encoding complexity and reduce the memory storage required for the parity-check matrix, which can be more easily built than others codes used in channel coding.

Quasi-cyclic low-density parity-check (QC-LDPC) codes are an important class of LDPC codes which can be encoded and decoded with low complexity and suitable for many applications. As the code dimension, which describes the number of protected information bits, is equal to the code length minus the rank of the parity-check matrix and the parity-check matrix for QC-LDPC codes is usually not full-rank, determining the rank of the parity-check matrix is of essential importance. In this paper, we study the rank of the parity-check matrix for QC-LDPC codes based on the associated polynomials for circulant matrices. A formula for the rank of the parity-check matrix with only one row-block is first derived. We then extend the result to matrices with two, three, or more row-blocks. Some bounds are also presented for matrices with arbitrary numbers of row-blocks. Furthermore, the exact rank is determined for a class of algebraically constructed parity-check matrices.

Designing good error correcting codes whose generator matrix has a support constraint, i.e., one for which only certain entries of the generator matrix are allowed to be nonzero, has found many recent applications, including in distributed coding and storage, multiple access networks, and weakly secure data exchange. The dual problem, where the parity check matrix has a support constraint, comes up in the design of locally repairable codes. The central problem here is to design codes with the largest possible minimum distance, subject to the given support constraint on the generator matrix. An upper bound on the minimum distance can be obtained through a set of singleton bounds, which can be alternatively thought of as a cut-set bound. Furthermore, it is well known that, if the field size is large enough, any random generator matrix obeying the support constraint will achieve the maximum minimum distance with high probability. Since random codes are not easy to decode, structured codes with efficient decoders, e.g., Reed-Solomon codes, are much more desirable. The GM-MDS conjecture of Dau et al states that the maximum minimum distance over all codes satisfying the generator matrix support constraint can be obtained by a Reed Solomon code. If true, this would have significant consequences. The conjecture has been proven for several special case: when the dimension of the code k is less than or equal to five, when the number of distinct support sets on the rows of the generator matrix m, say, is less than or equal to three, or when the generator matrix is sparsest and balanced. In this paper, we report on further progress on the GM-MDS conjecture. 1. In particular, we show that the conjecture is true for all m less than equal to six. This generalizes all previous known results (except for the sparsest and balanced case, which is a very special support constraint).

In this paper, we develop a simple matrix method of constructing a parity check matrix for non binary (5k, k; b, q, m) linear codes capable of correcting m repeated burst errors of length b or less.

This paper presents Bit error Rate performance Analysis of Quasi Cyclic Low Density Parity Check Codes (QC-LDPC) with girth 6 using Log Domain sum product and Simple Log Domain Sum Product Algorithm for Decoding. The approach to construct Parity Check matrix for LDPC codes is based on sparse Lower Upper decomposition. Then to create QC-LDPC matrix counter shifting, interleave mapping, Set XORing, Circulant Shifting and Randomization processes are being used. The constructed QC-LDPC codes is of a girth 6 on / code Rate have row weight 6 and column weight 3. Bit error rate performance is done through simulation to be calculated for various code length such as code I (960, 480), code II (1980, 990) and code III (1080, 540).

A new simplified structure of bit-interleaved coded modulation (BICM) for second generation digital video broadcasting (DVB) standards, such as DVB-T2, DVB-C2, and DVB-NGH is proposed. In the BICM of the DVB standards, parity and column-twist interleavers are employed in order to avoid possible performance degradation due to the structural weaknesses of the BICM scheme. In this paper, a new method is proposed of finding permutation-equivalent low-density parity-check codes that eliminate the BICM weaknesses without the column-twist interleaver, thereby simplifying the BICM structure of the DVB standards. The new code descriptions are found by applying a column permutation to the parity check matrices of the original codes in the DVB standards. The codes generated by these new descriptions have the same error correcting capability individually for a binary memoryless channel. However, the resulting BICM has a different structure that is free of weakness, called the less-capable check node.

Error-rate floor phenomenon is known to be a serious impediment to the use of low-density parity-check (LDPC) codes for some practical applications that demand high data reliability. In the case of binary erasure channels (BECs), certain error-prone patterns, known as stopping sets, are proven to cause this performance degradation. A possible approach to diminish this drawback over BECs is to eliminate stopping sets by parity-check matrix extension. Given a parity-check matrix $H$ , and a list $\mathcal{L} $ of its stopping sets, we present an integer linear programming (ILP) formulation to find a parity-check equation which eliminates the maximum number of stopping sets in $\mathcal{L} $ . One of the distinguishing advantages of the proposed scheme is its flexibility for modifications such as: limiting the weight of the new parity-check row, making the new row redundant or linearly independent, 4-cycle avoidance, and taking into account the sizes of stopping sets. Armed with these adjustments, the method can provide good performance improvements, as evidenced by simulation results. Furthermore, for a given $\varrho\in\mathbb{N} $ , by extending the basic formulation, we provide an ILP formulation for finding a set of size $\varrho$ of parity-check equations which can best eliminate the stopping sets in $\mathcal{L}$ , among all such sets.

This letter investigates a new class of index coding problems. One sender broadcasts packets to multiple users, each desiring a subset, by exploiting prior knowledge of linear combinations of packets. We refer to this class of problems as index coding with coded side-information. Our aim is to characterize the minimum index code length that the sender needs to transmit to simultaneously satisfy all user requests. We show that the optimal binary vector index code length is equal to the minimum rank (minrank) of a matrix whose elements consist of the sets of desired packet indices and side- information encoding matrices. This is the natural extension of matrix minrank in the presence of coded side information. Using the derived expression, we propose a greedy randomized algorithm to minimize the rank of the derived matrix., Comment: A short version will be appeared in IEEE Communications Letter

In this paper, we study linear receiver space-time block codes (L-STBCs). These codes are very important and applicable because the simplest decoders, namely, ZF and MMSE, can be implemented at the receiver to decode these codes. Design criterion of L-STBCs is the primary basis needed for research in this field. The only criterion put forth to date is based on two conditions on the equivalent channel matrix. In this paper, first, we propose a systematic guideline for determining the equivalent channel matrix of a wide range of L-STBCs, including all the existing L-STBCs, and then, we derive a new design criterion for these L-STBCs with only one condition on the code structure. In addition, we show that there is a strong connection between full-diversity L-STBCs and full-rank subspaces of matrices. Finally, L-STBCs with orthogonal equivalent channels are characterized.

In coding theory, we study various properties of codes for application in data compression, cryptography, error correction, and network coding. The study of codes is introduced in Information Theory, electrical engineering, mathematics, and computer sciences for the transmission of data through reliable and efficient methods. We have to consider how coding of messages can be done efficiently so that the maximum number of messages can be sent over a noiseless channel in a given time. Thus, the minimum value of mean codeword length subject to a given constraint on codeword lengths has to be founded. In this paper, we have introduced mean codeword length of orderαand typeβfor 1:1 codes and analyzed the relationship between average codeword length and fuzzy information measures for binary 1:1 codes. Further, noiseless coding theorem associated with fuzzy information measure has been established.

We prove that for every prime $p$ there exists a (0,1)-matrix $M$ of size $t_p(n,m)\times n$, where $t_p(n,m)=O(m+\frac{m\log \frac{n}{m}}{\log \min({m,p})})$ such that every $m$ columns of $M$ are linearly independent over $\mathbb{Z}_p$, the field of integers modulo $p$ (and therefore over any field of characteristic $p$ and over the field of real numbers $\mathbb{R}$). In coding theory this matrix is a parity-check (0,1)-matrix over $\mathbb{Z}_p$ of a linear code of minimal distance m+1. Using the Hamming bound (for $p

We present design principles for implementing decoders for low-density parity check codes in CMOL-type memristive circuits. The programmable nonvolatile connectivity enabled by the nanowire arrays in such circuits is used to map the parity check matrix of an LDPC code in the decoder, while decoding operations are realized by a cellular CMOS circuit structure. We perform detailed performance analysis and circuit simulations of example decoders, and estimate how CMOL and memristor characteristics such as the memristor OFF/ON resistance ratio, nanowire resistance, and the total capacitance of the nanowire array affect decoder specification and performance. We also analyze how variation in circuit characteristics and persistent device defects affect the decoders.

In this paper, we aim at utilizing the Cayley tables demonstrated by the Authors[1] in the construction of a Generator/Parity check Matrix in standard form for a Code say C Our goal is achieved first by converting the Cayley tables in [1] using Mod2 arithmetic into a Matrix with entries from the binary field. Echelon Row operations are then performed (carried out) on the matrix in line with existing algorithms and propositions to obtain a matrix say G whose rows spans C and a matrix say H whose rows spans C⊥, the dual code of C, where G and H are given as, G = (Ik | X ) and H= ( -XT | In-k ). The report by Williem (2011) that the adjacency Matrix of a graph can be interpreted as the generator matrix of a Code [3] is in this context extended to the Cayley table which generates matrices from the permutations of points of the AUNU numbers of prime cardinality.

For practical applications in forward error correction, the importance of a systematic codeword cannot be overemphasized. Thus, this paper proposes the construction of a systematic quasi-cyclic (QC) LDPC code. This systematic structure is achieved by a row reduction technique different from the conventional Gaussian elimination method. This row reduction technique has the advantage of being easier to implement when compared to Gaussian row reduction techniques. The proposed row reduction technique maintains the quasi cyclic structure and the sparsity of the QC-LDPC parity check matrix while providing a low complexity approach to the construction of the generator matrix. In addition, the proposed construction exhibits a good BER performance for high rate codes.

The Parity check Transformation Algorithm (PTA) is a recently developed symbol wise soft decision decoding algorithm for Reed Solomon codes. The algorithm has been shown in literature to outperform widely used Reed Solomon decoders including the Koetter and Vardy (KV) algorithm. The PTA gets its name from the fact that it transforms the parity check matrix of the Reed Solomon code after every iteration depending on the reliability of each symbol initially obtained from the output of the channel. The major disadvantage of the PTA algorithm is that it requires numerous iterations to decode. In this paper an extension of the algorithm is developed with the aim of improving the performance and reducing the number of iterations required to decode. Simulations run show that using an extended H matrix provides a significant reduction in the number of iterations required to decode without any SER performance loss.

International audience; We consider the joint detection and decoding of m-sequences. The receiver has to decide whether an m-sequence is received and possibly to decode its initial state. To do so, it implements an iterative message-passing decoding algorithm that operates on a parity check matrix, built upon a number of reference parity-check equations satisfied by the m-sequence. This matrix concatenates several elementary parity check matrices which are derived from reference equations. Unlike the conventional decoding case, the detection problem imposes to consider false alarms that may occur when the decoder is only fed with noise. While absorbing sets are known to be responsible for the error floor phenomenon of iterative message-passing decoders, we show that they may have a beneficial effect on the detection performance, in that they may prevent the decoder to produce false alarms. We further compute the number of hybrid cycles of length 6 and 8 in the Tanner graph of the decoder and use the minimization of this number as criterion to derive an algorithm for selecting the reference parity check equations. This algorithm was found to be efficient for minimizing the probability of false alarm and decreases also the probability of wrong detection in the very small SNR region. This has been achieved at the cost of a reduction of the probability of correct detection.

A novel scheme is presented for encoding and decoding of Reed-Solomon codes of prime lengths. Encoding is performed on a collection of codewords which are mapped through Galois Fourier transform into a codeword in a low-density parity-check code with a binary parity-check matrix for transmission. Using this matrix, a binary iterative soft-decision decoding algorithm is applied to jointly decode a collection of codewords in the Reed-Solomon code. By allowing information sharing among the received vectors corresponding to the code-words in the collection, the proposed decoding scheme achieves superior performance over algorithms decoding individual Reed-Solomon codewords including maximum likelihood decoding.

A complete decoder is one that guarantees to decode a received vector to its nearest codeword. For the design of an efficient complete decoding algorithm, storage demand and decoding complexity are two essential factors. Along this consideration, the Zero-Guards algorithm provides a significant improvement as the number of vectors required to be stored has been made much less than what is required by the conventional standard array decoding. When being applied to certain block codes, however, it may be inefficient when code length is short. At this background, a new step-by-step complete decoding algorithm for cyclic codes is proposed in this work. Based on a newly devised transfer function, our algorithm can achieve a better decoding efficiency than the Zero-Guards algorithm, while keeping a smaller number of vectors for most of the cyclic codes examined.

We construct new families of completely regular codes by concatenation methods. By combining parity check matrices of cyclic Hamming codes, we obtain families of completely regular codes. In all cases, we compute the intersection array of these codes. As a result, we find some non-equivalent completely regular codes, over the same finite field, with the same parameters and intersection array. We also study when the extension of these codes gives completely regular codes. Some of these new codes are completely transitive.

Partial-MDS (PMDS) codes are a family of locally repairable codes, mainly used for distributed storage. They are defined to be able to correct any pattern of $s$ additional erasures, after a given number of erasures per locality group have occurred. This makes them also maximally recoverable (MR) codes, another class of locally repairable codes. It is known that MR codes in general, and PMDS codes in particular, exist for any set of parameters, if the field size is large enough. Moreover, some explicit constructions of PMDS codes are known, mostly (but not always) with a strong restriction on the number of erasures that can be corrected per locality group. In this paper we generalize the notion of PMDS codes to allow locality groups of different sizes. We give a general construction of such PMDS codes with $s=1$ global parity, i.e., one additional erasure can be corrected. Furthermore, we show that all PMDS codes for the given parameters are of this form, i.e., we give a classification of these codes. This implies a necessary and sufficient condition on the underlying field size for the existence of these codes (assuming that the MDS conjecture is true). For some parameter sets our generalized construction gives rise to PMDS codes with a smaller field size than any other known construction.

A concatenated coding scheme over binary memoryless symmetric (BMS) channels using a polarization transformation followed by outer sub-codes is analyzed. Achievable error exponents and upper bounds on the error rate are derived. The first bound is obtained using outer codes which are typical linear codes from the ensemble of parity check matrices whose elements are chosen independently and uniformly. As a byproduct of this bound, it determines the required rate split of the total rate to the rates of the outer codes. A lower bound on the error exponent that holds for all BMS channels with a given capacity is then derived. Improved bounds and approximations for finite blocklength codes using channel dispersions (normal approximation), as well as converse and approximate converse results, are also obtained. The bounds are compared to actual simulation results from the literature. For the cases considered, when transmitting over the binary input additive white Gaussian noise channel, there was only a small gap between the normal approximation prediction and the actual error rate of concatenated BCH-polar codes., Comment: Submitted to IEEE Transactions on Information Theory

The efficient encoding of quasi-cyclic (QC) low-density parity-check (LDPC) codes is based on generator matrices in systematic-circulant (SC) form. The cost of the encoders of QC-LDPC codes mainly depends on the number of non-zero entries in the SC generator matrices. This study introduces a novel construction of SC generator matrices based on matrix transformations via Galois Fourier transform. By revealing the structure of SC generator matrices in the transform domain, an algorithm is proposed to reduce the density of the generator matrices of QC-LDPC codes. Furthermore, a tight upper bound on ranks of QC matrices is derived. Based on the bound, rank distributions of parity-check matrices and generator matrices in the transform domain illustrate the efficiency of the proposed algorithm. Simulation results show that the density of their SC generator matrices can be significantly decreased with moderate computational complexity.