共查询到20条相似文献,搜索用时 15 毫秒
1.
A free Z4 code C may be decoded by decoding its canonical image C macr over Z2 twice in succession. Hence, a Chase decoder for C could employ as its hard-decision (HD) decoder, a two-stage decoder which performs HD decoding on C macr in each stage. Alternatively, one could have a two-stage soft-decision decoder by employing a Chase decoder for C macr in each stage. We demonstrate that the latter approach can offer a significant reduction in complexity over the other, with little or no price to pay in terms of word error rate performance, particularly at low to moderate code rates. 相似文献
2.
Mitzenmacher M. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2006,52(12):5496-5501
We demonstrate polynomial-time deletion codes based on the verification-based decoding paradigm that come arbitrarily close to capacity. The random deletion channel takes n symbols from a q-ary alphabet, and each symbol is deleted independently with probability p. Taking advantage of recent improvements on the results of Luby and Mitzenmacher for verification-based decoding by Shokrollahi and Wang, we show how to design for any epsi>0 and sufficiently large n and q deletion codes with the following properties: the rate is (1-p)(1-epsi), the failure probability is nO(1/epsi2)/q, and the computational complexity for encoding and decoding is nO(1/epsi2)log q. We also extend these schemes to obtain the same results even if the undeleted symbols are also transposed arbitrarily, and if a sufficiently small number of random symbols are inserted 相似文献
3.
Roth R.M. Skachek V. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2006,52(8):3650-3661
A construction of expander codes is presented with the following three properties: i) the codes lie close to the Singleton bound, ii) they can be encoded in time complexity that is linear in their code length, and iii) they have a linear-time bounded-distance decoder. By using a version of the decoder that corrects also erasures, the codes can replace maximum-distance separable (MDS) outer codes in concatenated constructions, thus resulting in linear-time encodable and decodable codes that approach the Zyablov bound or the capacity of memoryless channels. The presented construction improves on an earlier result by Guruswami and Indyk in that any rate and relative minimum distance that lies below the Singleton bound is attainable for a significantly smaller alphabet size 相似文献
4.
Guruswami V. Rudra A. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2008,54(1):135-150
In this paper, we present error-correcting codes that achieve the information-theoretically best possible tradeoff between the rate and error-correction radius. Specifically, for every 0 < R < 1 and epsiv < 0, we present an explicit construction of error-correcting codes of rate that can be list decoded in polynomial time up to a fraction (1- R - epsiv) of worst-case errors. At least theoretically, this meets one of the central challenges in algorithmic coding theory. Our codes are simple to describe: they are folded Reed-Solomon codes, which are in fact exactly Reed-Solomon (RS) codes, but viewed as a code over a larger alphabet by careful bundling of codeword symbols. Given the ubiquity of RS codes, this is an appealing feature of our result, and in fact our methods directly yield better decoding algorithms for RS codes when errors occur in phased bursts. The alphabet size of these folded RS codes is polynomial in the block length. We are able to reduce this to a constant (depending on epsiv) using existing ideas concerning ldquolist recoveryrdquo and expander-based codes. Concatenating the folded RS codes with suitable inner codes, we get binary codes that can be efficiently decoded up to twice the radius achieved by the standard GMD decoding. 相似文献
5.
《Communications, IEEE Transactions on》2005,53(7):1232-1232
Reduced-Complexity Decoding of LDPC Codes Various log-likelihood-ratio-based belief-propagation (LLR- BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representation of the decoding computations are shown to achieve a reduction in complexity, by simplifying the check-node update or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from a performance, latency, computational complexity, and memory-requirement perspective. 相似文献
6.
Golay码的快速译码 总被引:2,自引:0,他引:2
本文利用Golay码的代数结构给出了二元(23,12,7)Golay码及三元(11,6,5)Golay码新的译码算法。对于二元Golay码,所提的算法的最坏时间复杂性为534次mod2加法,比已知的同类译码算法的时间复杂性都小;平均时间复杂性为224次mod2加法,比目前已知的最快的译码算法的平均时间复杂性279次mod2加法还要小。对于三元Golay码,所提算法的最坏时间复杂性为123次mod3加法,平均时间复杂性为85次mod3加法,比同类的算法都快。此外,这里给出的算法结构简单,易于实现。 相似文献
7.
The classical Viterbi decoder recursively finds the trellis path (code word) closest to the received data. Given the received data, the syndrome decoder first forms a syndrome, instead. A recursive algorithm like Viterbi's is used to determine the noise sequence of minimum Hamming weight that can be a possible cause of this syndrome. Given the estimate of the noise sequence, one derives an estimate of the original data sequence. While the bit error probability of the syndrome decoder is no different from that of the classical Viterbi decoder, the syndrome decoder can be implemented using a read only memory (ROM), thus obtaining a considerable saving in hardware. 相似文献
8.
《Selected Areas in Communications, IEEE Journal on》2006,24(8):1603-1613
We consider the decoding problem for low-density parity-check codes, and apply nonlinear programming methods. This extends previous work using linear programming (LP) to decode linear block codes. First, a multistage LP decoder based on the branch-and-bound method is proposed. This decoder makes use of the maximum-likelihood-certificate property of the LP decoder to refine the results when an error is reported. Second, we transform the original LP decoding formulation into a box-constrained quadratic programming form. Efficient linear-time parallel and serial decoding algorithms are proposed and their convergence properties are investigated. Extensive simulation studies are performed to assess the performance of the proposed decoders. It is seen that the proposed multistage LP decoder outperforms the conventional sum-product (SP) decoder considerably for low-density parity-check (LDPC) codes with short to medium block length. The proposed box-constrained quadratic programming decoder has less complexity than the SP decoder and yields much better performance for LDPC codes with regular structure. 相似文献
9.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》2008,54(3):1036-1049
10.
本文给出了几何广义RS码的一种有效译码算法,该算法可对任意错误个数不超过「(d-1)/2」的接收码字进行译码,其复杂度仅为O(n^3)。 相似文献
11.
本文提出一种在形式上类似于卷积码的序列译码的一般线性分组码的软判决伪序列译码算法,利用广义限译码原理及二元有向树的性质与分枝限搜索技术,降低了译码复杂性,其设备复杂度小于Chase译码器,模拟结果表明,该算法的误码输出性能接近维持比较最大似然译码,好于ChaseⅡ算法,且译码速度与ChaseⅡ算法接近。 相似文献
12.
It is shown that a convolutional code can be decoded with a sliding-block decoder, a time-invariant nonlinear digital filter with finite memory and delay. If the memory and delay are small, then the sliding-block decoder can be implemented as a table lookup procedure in ROM, resulting in a low cost, high speed, and high reliability decoder. 相似文献
13.
针对RS码与LDPC码的串行级联结构,提出了一种基于自适应置信传播(ABP)的联合迭代译码方法.译码时,LDPC码置信传播译码器输出的软信息作为RS码ABP译码器的输入;经过一定迭代译码后,RS码译码器输出的软信息又作为LDPC译码器的输入.软输入软输出的RS译码器与LDPC译码器之间经过多次信息传递,译码性能有很大提高.码长中等的LDPC码采用这种级联方案,可以有效克服短环的影响,消除错误平层.仿真结果显示:AWGN信道下这种基于ABP的RS码与LDPC码的联合迭代译码方案可以获得约0.8 dB的增益. 相似文献
14.
Chunlong Bai Bartosz Mielczarek Witold A. Krzymien Ivan J. Fair 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2007,53(2):615-627
A list decoder generates a list of more than one codeword candidates, and decoding is erroneous if the transmitted codeword is not included in the list. This decoding strategy can be implemented in a system that employs an inner error correcting code and an outer error detecting code that is used to choose the correct codeword from the list. Probability of codeword error analysis for a linear block code with list decoding is typically based on the "worst case" lower bound on the effective weights of codewords for list decoding evaluated from the weight enumerating function of the code. In this paper, the concepts of generalized pairwise error event and effective weight enumerating function are proposed for evaluation of the probability of codeword error of linear block codes with list decoding. Geometrical analysis shows that the effective Euclidean distances are not necessarily as low as those predicted by the lower bound. An approach to evaluate the effective weight enumerating function of a particular code with list decoding is proposed. The effective Euclidean distances for decisions in each pairwise error event are evaluated taking into consideration the actual Hamming distance relationships between codewords, which relaxes the pessimistic assumptions upon which the traditional lower bound analysis is based. Using the effective weight enumerating function, a more accurate approximation is achieved for the probability of codeword error of the code with list decoding. The proposed approach is applied to codes of practical interest, including terminated convolutional codes and turbo codes with the parallel concatenation structure 相似文献
15.
A new practical method for decoding low-density parity check (LDPC) codes is presented. The followed approach involves reformulating the parity check equations using nonlinear functions of a specific form, defined over Rrho, where rho denotes the check node degree. By constraining the inputs to these functions in the closed convex subset [0,1]rho ("box" set) of Rrho, and also by exploiting their form, a multimodal objective function that entails the code constraints is formulated. The gradient projection algorithm is then used for searching for a valid codeword that lies in the vicinity of the channel observation. The computational complexity of the new decoding technique is practically sub-linearly dependent on the code's length, while processing on each variable node can be performed in parallel allowing very low decoding latencies. Simulation results show that convergence is achieved within 10 iterations, although some performance degradations relative to the belief propagation (BP) algorithm are observed 相似文献
16.
Straightforward implementation of a maximum likelihood decoder implies a complexity that grows algebraically with the inverse of error probability. Forney has suggested an approach, concatenation, for which error probability decreases exponentially with increasing complexity. This paper presents the results of an evaluation of a particular concatenation system, structurally similar to the hybrid system of Falconer, employing a Reed-Solomon outer code and an inner convolutional code. The inner decoder is a Viterbi decoder of constraint length less than the corresponding encoding constraint length (nonmaximum likelihood). The outer decoder assumes one of three possible forms, all employing the likelihood information developed by the inner decoder to assist in outer decoding. Error corrections and erasure fill-ins achieved by the outer decoder are fed back to the inner decoder. Performance is evaluated through computer simulation. The three outer decoders are found to provide approximately the same performance, all yielding low error probabilities at rates somewhat above Rcomp of sequential decoding and at signal energy to noise density ratios per information bit around 1.7 dB. 相似文献
17.
18.
LDPC卷积码的快速收敛译码 总被引:2,自引:2,他引:0
采用串行消息传递策略,文中提出了LDPC卷积码的一种改进的流水线式译码器.分析和仿真结果均表明改进的译码器在不增加单个处理器计算复杂度的前提下,仅通过改变消息传递方式就能够大大加速译码收敛速率,与原译码器相比大约可以节省一半的处理器. 相似文献
19.
In this paper, we propose a new reduced-complexity decoding algorithm of Low-Density Parity-Check (LDPC) codes, called Belief-Propagation-Approximated (BPA) algorithm, which utilizes the idea of normalization and translates approximately the intricate nonlinear operation in the check nodes of the original BP algorithm to only one operation of looking up the table. The normalization factors can be obtained by simulation, or theoretically. Simulation results demonstrate that BPA algorithm exhibits fairly satisfactory bit error performance on the Additive White Gaussian Noise (AWGN) channel. 相似文献
20.
卷积码及维特比译码在卫星通信中的应用 总被引:1,自引:0,他引:1
在功率受限的卫星信道中,卷积码与BPSK(或QPSK)结合在一起被看作是可靠通信的一种有效的系统。该文讨论了卫星通信信道特性,介绍了卷积编码、BPSK信号和软判决,给出了卷积码最大似然译码——维特比译码算法。 相似文献