共查询到20条相似文献,搜索用时 31 毫秒
1.
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加法,比同类的算法都快。此外,这里给出的算法结构简单,易于实现。 相似文献
2.
A decoding algorithm based on revised syndromes to decode the binary (23,12,7) Golay code is presented. The algorithm strongly depends on the algebraic properties of the code. For the algorithm, the worst complexity is about 683 mod2 additions, which is less than that of the algorithms available for the code, the average complexity is approximately 319 mod2 additions, which is slightly more than that of Blaum's algorithm for the code. 相似文献
3.
A decoding algorithm based on revised syndromes to decode the binary (23,12,7) Golay code is presented. The algorithm strongly
depends on the algebraic properties of the code. For the algorithm, the worst complexity is about 683 mod2 additions, which
is less than that of the algorithms available for the code, the average complexity is approximately 319 mod2 additions, which
is slightly more than that of Blaum’s algorithm for the code.
Supported by the National Natural Science Foundation of China 相似文献
4.
Two recursive-least-squares ladder algorithms for implementation on triangular systolic arrays are presented. The first algorithm computes transversal forward/backward predictor coefficients, ladder reflection coefficients, and forward/backward residual energies. This algorithm has a complexity of three multiplications and additions per rotational (triangular array) element. A second algorithm is presented that facilitates the computation of only the ladder reflection coefficients and the forward/backward residual energies at a cost of two multiplications and additions per rotational element. This way, both algorithms are computationally more efficient than the traditional recursive QR decomposition (Gentleman and Kung array) for any order. The second algorithm is more efficient than Cioffi's pipelineable linear array fast QR adaptive filter for an order of less than 22 in the prewindowed case, and more efficient than the fast QR for an order of less than 43 in the more general covariance case. A comparison of the presented algorithms and the prominent QR methods is given. The algorithms remain unchanged and the number of arithmetic operations is not increased when finite duration windows are used. The algorithms are based entirely on numerically stable and robust covariance recursions 相似文献
5.
《Signal Processing, IEEE Transactions on》2009,57(3):1010-1020
6.
7.
We present a frame synchronization algorithm for low‐density parity‐check (LDPC) coded burst transmissions, which combines a conventional pilots‐assisted frame synchronization algorithm and a code‐aided algorithm based on the mean magnitude of the soft outputs from the LDPC decoder. With moderate computational complexity, the proposed algorithm is more efficient in bandwidth than conventional pilots‐assisted algorithms. When compared with other code‐aided algorithms, the proposed algorithm offers a better trade‐off between complexity and performance. Simulation results in the case of an 8‐PSK system with (1944, 972) LDPC code show that the proposed algorithm can achieve a performance equivalent to that of the perfect frame synchronization, with a bandwidth efficiency loss of 0.06 dB due to the use of pilot symbols. 相似文献
8.
Reed I.S. Shih M.-T. Truong T.K. Hendon E. Tufts D.W. 《Signal Processing, IEEE Transactions on》1992,40(5):1122-1133
The arithmetic Fourier transform (AFT) is a number-theoretic approach to Fourier analysis which has been shown to perform competitively with the classical FFT in terms of accuracy, complexity, and speed. Theorems developed by I.S. Reed et al. (1990) for the AFT algorithm are used here to derive the original AFT algorithm which Bruns found in 1903. This is shown to yield an algorithm of less complexity and of improved performance over certain AFT algorithms. A VLSI architecture is suggested for this simplified AFT algorithm. This architecture uses a butterfly structure which reduces the number of additions by 25% of that used in the direct method 相似文献
9.
10.
Noncoherent decoding of trellis codes using multiple-symbol overlapped observations was shown previously to achieve close to the coherent performance. Optimal decoding by the Viterbi algorithm for L-symbol observations requires a number of states which grows exponentially with L. Two novel suboptimal algorithms are presented, for which the number of states is the same as the original code, yielding a complexity depending weakly on L. For practical values of L, both algorithms are substantially less complex than the optimal algorithm. The first algorithm, the basic decision feedback algorithm (BDFA), is a low complexity feedback decoding scheme, based on the Viterbi algorithm. This algorithm is shown to suffer from increased error probability and from error propagation. A slight modification to this algorithm can, in most cases, reduce these effects significantly. The second algorithm uses the BDFA as a basic building block. This algorithm is based on a novel concept called “estimated future” and its performance is very close to optimum for most practical eases with some additional complexity and memory requirements as compared to the first algorithm. Performance analysis and simulation results are also given 相似文献
11.
Forney G.D. Jr. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1989,35(4):906-909
An algorithm is given that decodes the Leech lattice with not much more than twice the complexity of soft-decision decoding of the Golay code. The algorithm has the same effective minimum distance as maximum-likelihood decoding and increases the effective error coefficient by less than a factor or two. The algorithm can be recognized as a member of the class of multistage algorithms that are applicable to hierarchical constructions. It is readily generalized to lattices that can be expressed in terms of binary code formulas, and in particular to construction B lattices 相似文献
12.
Ashikhmin A. Litsyn S. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2004,50(8):1812-1818
A maximum a posteriori (MAP) probability decoder of a block code minimizes the probability of error for each transmitted symbol separately. The standard way of implementing MAP decoding of a linear code is the Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm, which is based on a trellis representation of the code. The complexity of the BCJR algorithm for the first-order Reed-Muller (RM-1) codes and Hamming codes is proportional to n/sup 2/, where n is the code's length. In this correspondence, we present new MAP decoding algorithms for binary and nonbinary RM-1 and Hamming codes. The proposed algorithms have complexities proportional to q/sup 2/n log/sub q/n, where q is the alphabet size. In particular, for the binary codes this yields complexity of order n log n. 相似文献
13.
This paper presents two scheduling algorithms, MWF2Q+ and MDRR, for multiple classes of service over the same spectrum in the forward link of the UMTS network. These scheduling algorithms can allocate bandwidth in proportion to weights of flows sharing the channel, and assign OVSF code to backlogged flows on a frame‐by‐frame basis. The MWF2Q+ algorithm has better fairness properties while the MDRR algorithm requires less computational complexity and space complexity. The fairness properties of these scheduling algorithms are analysed in this paper. Our simulation results show that these two algorithms support multiple traffic sources with heterogeneous rate guarantees while fully utilizing the system bandwidth. The impact of self‐similar traffic is also addressed in our simulations. Copyright © 2005 John Wiley & Sons, Ltd. 相似文献
14.
15.
改进的离散字母表迭代译码算法研究 总被引:1,自引:0,他引:1
为了优化LDPC迭代译码性能和降低算法复杂度,提出了一种改进的基于Gallager A算法的2b离散字母表迭代译码算法。在每一轮迭代中,Tanner图上的校验节点与变量节点之间所传递的消息有1b表示符号值,另1b反映码字结构特性,其中变量节点更新规则是通过查表法来实现的。在二元对称信道下针对列重为3的规则LDPC码做了仿真实验,仿真结果表明该算法性能明显优于原算法,并且具有较低的复杂度。 相似文献
16.
Effros M. 《Proceedings of the IEEE. Institute of Electrical and Electronics Engineers》2000,88(11):1703-1712
This paper introduces a new data compression algorithm. The goal underlying this new code design is to achieve a single lossless compression algorithm with the excellent compression ratios of the prediction by partial mapping (PPM) algorithms and the low complexity of codes based on the Burrows Wheeler Transform (BWT). Like the BWT-based codes, the proposed algorithm requires worst case O(n) computational complexity and memory; in contrast, the unbounded-context PPM algorithm, called PPM*, requires worst case O(n2) computational complexity. Like PPM*, the proposed algorithm allows the use of unbounded contexts. Using standard data sets for comparison, the proposed algorithm achieves compression performance better than that of the BWT-based codes and comparable to that of PPM*. In particular, the proposed algorithm yields an average rate of 2.29 bits per character (bpc) on the Calgary corpus; this result compares favorably with the 2.33 and 2.34 bpc of PPM5 and PPM* (PPM algorithms), the 2.43 bpc of BW94 (the original BWT-based code), and the 3.64 and 2.69 bpc of compress and gzip (popular Unix compression algorithms based on Lempel-Ziv (LZ) coding techniques) on the same data set. The given code does not, however, match the best reported compression performance-2.12 bpc with PPMZ9-listed on the Calgary corpus results web page at the time of this publication. Results on the Canterbury corpus give a similar relative standing. The proposed algorithm gives an average rate of 2.15 bpc on the Canterbury corpus, while the Canterbury corpus web page gives average rates of 1.99 bpc for PPMZ9, 2.11 bpc for PPM5, 2.15 bpc for PPM7, 2.23 bpc for BZIP2 (a popular BWT-based code), and 3.31 and 2.53 bpc for compress and gzip, respectively 相似文献
17.
A new scheme for reducing the numerical complexity of the standard B.C.H. and Reed?Solomon (R.S.) decoding algorithms is developed. Specifically, the process of calculating syndromes over GF(2m) is shown to require only a small fraction of the number of multiplications and additions that is required by using standard methods. As an example, the calculation of the 32 syndromes of the (255, 223, 33) Reed?Solomon code (NASA standard for concatenation with convolutional codes) is shown to require 90% fewer multiplications and 78% fewer additions than the conventional method of computation. A computer simulation also verifies these results. 相似文献
18.
19.
针对目前高斯消元法在归零Turbo码长、帧同步等参数识别过程存在容错性能低且计算复杂度高的缺点,该文提出一种低信噪比(SNR)下基于差分似然差(DLD)的识别算法。首先通过定义差分似然差的概念,利用归零Turbo码帧头两码元差分似然差为正值(“+”)的特性,构建分析矩阵实现码长的识别;其次,提出基于最小错误判决准则下的差分似然差“+”位置门限判决方法,完成帧同步;最后,从工程实际出发,遍历寄存器个数的可能值,实现码率、寄存器个数以及交织长度识别。仿真实验表明:所提算法对于归零Turbo码码长、帧同步等参数识别有效,差分似然差“+”位置分布与分析的数据结构特征一致,判决门限能够有效判断差分似然差“+”位置,同时,算法容错性能较强,在信噪比为–5 dB条件下,码长、帧同步等参数识别率能够达到90%以上,并且算法的复杂度远小于现有算法。 相似文献