We propose a new family of asymptotically good binary codes, generalizing previous constructions of expander codes to t-uniform hypergraphs. We also describe an efficient decoding algorithm for these codes, that for a...
详细信息
We propose a new family of asymptotically good binary codes, generalizing previous constructions of expander codes to t-uniform hypergraphs. We also describe an efficient decoding algorithm for these codes, that for a certain region of rates improves the known results for decoding distance of expander codes. The construction is based on hypergraphs with a certain "expansion" property called herein chomogeneity. For t-uniform t-partite Delta-regular hypergraphs, the expansion property required is roughly as follows: given t sets, A(1),..., A(t), one at each side, the number of hyper-edges with one vertex in each set is approximately what would be expected had the edges been chosen at random. We show that in an appropriate random model, almost all hypergraphs have this property, and also present an explicit construction of such hypergraphs. Having a family of such hypergraphs, and a small code C-0 subset of or equal to {0, 1}(Delta), with relative distance So and rate R-0, we construct "hypergraphs codes". These have rate greater than or equal to R-0 - (t - 1), and relative distance greater than or equal todelta(0)(t(t-1)) -o(1). When t = 2l we also suggest a decoding algorithm, and prove that the fraction of errors that it decodes correctly is at least ((2l-1)(l))(-1/l). (delta(0)/2)((l+1)/l) - o(1). In both cases, the o(1) is an additive term that tends to 0 as the length of the hypergraph code tends to infinity. (C) 2003 Elsevier Ltd. All rights reserved.
In this paper, a new decoding algorithm is proposed in which high-dimensional coding is done in a parity check code (high-dimensional ring code). The decoding method for the previously reported ring code has a complex...
详细信息
In this paper, a new decoding algorithm is proposed in which high-dimensional coding is done in a parity check code (high-dimensional ring code). The decoding method for the previously reported ring code has a complex correcting algorithm and requires much calculation time. We have focused on the point that a high-dimensional ring code can be divided into a number of two-dimensional ring codes, and by repeating the error correction of two-dimensional ring codes that requires small computation, we can perform error correction of high-dimensional ring codes. This decoding algorithm has a correction ability similar to the conventional decoding algorithms but with less computation. Moreover, when the error rate is high, random error and burst errors are mixed and an error correcting code is needed. However, since the decoding algorithm of the proposed code has a provision for dimensional division and the error generated on the transmitted block can be uniformly distributed on each two-dimensional plane, the error on the channel in the two-dimensional plane becomes random and error correction can be done efficiently. Moreover, if analysis or simulation increases the number of dimensions, then the correction ability is increased and the limit of the correction ability is determined from the size m of the code. The performance of convolutional codes and Reed Solomon codes is compared and it is shown that the ring code has high processing gain of error correction and that if the threshold point of correction lies in the high-error-rate region, then the decoding error rate is small and this code can be applied to high-error-rate correction. (C) 2001 Scripta Technica.
We first prove that every Hermitian code is a direct sum of concatenated Reed-Solomon codes over GF(q(2)), which provides a new method to calculate the dimension of the Hermitian code. Based on this, we present a new ...
详细信息
ISBN:
(纸本)0780379748
We first prove that every Hermitian code is a direct sum of concatenated Reed-Solomon codes over GF(q(2)), which provides a new method to calculate the dimension of the Hermitian code. Based on this, we present a new decoding algorithm for Hermitian code. Our algorithm is especially efficient in decoding burst errors. Finally, a method to optimize Hermitian code is obtained. The optimized code maintains the same dimension and error correctability, but the complexity for burst error correction can be reduced from O(n(5/3)) to O(n).
A step-by-step decoding algorithm is proposed for double-error-correcting Reed-Solomon codes of length n = 2(m)-1. Since the decoding algorithm can directly find the error value at the highest-order position in a rece...
详细信息
A step-by-step decoding algorithm is proposed for double-error-correcting Reed-Solomon codes of length n = 2(m)-1. Since the decoding algorithm can directly find the error value at the highest-order position in a received vector without determining the error location polynomial, the decoding procedure is very simple and regular;therefore it is suitable for hardware implementation.
This paper first transforms the Huffmann tree into a single-side growing Huffman tree, then presents a memory-efficient data structure to represent the single-side growing Huffman tree, which requires (n + d)[log(2)n]...
详细信息
This paper first transforms the Huffmann tree into a single-side growing Huffman tree, then presents a memory-efficient data structure to represent the single-side growing Huffman tree, which requires (n + d)[log(2)n]-bits memory space, where n is the number of source symbols and d is the depth of the Huffman tree. Based on the proposed data structure, we present an O(d)-time Huffman decoding algorithm. Using the same example, the memory required in our decoding algorithm is much less than that of [3], We finally modify our proposed data structure to design an O(1)-time parallel Huffman decoding algorithm on a concurrent read exclusive write parallel random-access machine (CREW PRAM) using d processors. (C) 2000 Elsevier Science B.V. All rights reserved.
We consider the task of reconstructing a curve in constant dimensional space from noisy data. We consider curves of the form C = [(x,y1,•••,yc) | yj = pj(x)], where the pj's are polynomials of low degree. Given n ...
详细信息
ISBN:
(纸本)9781581136746
We consider the task of reconstructing a curve in constant dimensional space from noisy data. We consider curves of the form C = [(x,y1,•••,yc) | yj = pj(x)], where the pj's are polynomials of low degree. Given n points in (c+1)-dimensional space, such that t of these lie on some such unknown curve C while the other n-t are chosen randomly and independently, we give an efficient algorithm to recover the curve C and the identity of the good points. The success of our algorithm depends on the relation between n, t, c and the degree of the curve C, requiring t = Ω (n deg(C)) 1/(c+1). This generalizes, in the restricted setting of random errors, the work of Sudan (J. Complexity, 1997) and of Guruswami and Sudan (IEEE Trans. Inf. Th. 1999) that considered the case c=1.
A new step-by-step decoding algorithm for decoding Reed-Solomon codes over GF(2(m)) is presented. Based on several properties of the syndrome matrices, the new step-by-step decoding algorithm can directly determine wh...
详细信息
A new step-by-step decoding algorithm for decoding Reed-Solomon codes over GF(2(m)) is presented. Based on several properties of the syndrome matrices, the new step-by-step decoding algorithm can directly determine whether every received symbol is an error locator, The detection of error location is based only on the determinant of a v x v syndrome matrix, where v is the number of errors. When an error location is found, its corresponding error value can also be determined by performing a determinant division operation between two syndrome matrices. The new decoding algorithm can significantly reduce computation complexity and improve the decoding speed compared with the conventional step-by-step decoding algorithm.
Parallel concatenated spa ce time trellis code modulation, called Turbo STCM, can efficiently increase the coding gains of the space time codes. However, the complexity of the iterat iv e decoding restricts its ap...
详细信息
Parallel concatenated spa ce time trellis code modulation, called Turbo STCM, can efficiently increase the coding gains of the space time codes. However, the complexity of the iterat iv e decoding restricts its application. This paper introduces a lower complex deco ding algorithm based on soft output Viterbi algorithm (SOVA) for Turbo STCM. S imulational results show that the new SOVA algorithm for the Turbo STCM outperf orms the original space time trellis code (STTC) by 4~6 dB. At the same time, compared with the Max Log MAP (maximum a posteriori) algorithm, the new scheme requires a lower complexity and approaches the performance of Turbo STCM decod ing w ith Max Log MAP.
An investigation into the turbo decoder is presented. It was carried out to determine whether the decoded bit sequence constitutes a (at least) local maximum in the likelihood between possible codewords in the composi...
详细信息
An investigation into the turbo decoder is presented. It was carried out to determine whether the decoded bit sequence constitutes a (at least) local maximum in the likelihood between possible codewords in the composite code trellis. The answer was obtained experimentally using a modified iterative turbo decoder. Results show that the turbo decoder does not necessarily lead to a maximum likelihood sequence estimator being realised for the composite code. Moreover, finding a closer code in a Euclidean distance sense only degrades the bit error rate of the system.
A new class of nested linear block code is introduced. The codes of this class, referred to as nested codes. cover a wide range of code length and rates. The parity check matrix of a nested code is constructed from tw...
详细信息
A new class of nested linear block code is introduced. The codes of this class, referred to as nested codes. cover a wide range of code length and rates. The parity check matrix of a nested code is constructed from two other linear block codes. Although the rates of the resulting codes are not optimal. the codes nevertheless exhibit some useful properties: in particular. they have a well-defined mathematical structure. which leads to a fast and simple decoding algorithm.
暂无评论