Golay码的快速译码

本文利用Ｇｏｌａｙ码的代数结构给出了二元（２３，１２，７）Ｇｏｌａｙ码及三元（１１，６，５）Ｇｏｌａｙ码新的译码算法。对于二元Ｇｏｌａｙ码，所提的算法的最坏时间复杂性为５３４次ｍｏｄ２加法，比已知的同类译码算法的时间复杂性都小；平均时间复杂性为２２４次ｍｏｄ２加法，比目前已知的最快的译码算法的平均时间复杂性２７９次ｍｏｄ２加法还要小。对于三元Ｇｏｌａｙ码，所提算法的最坏时间复杂性为１２３次ｍｏｄ３加法，平均时间复杂性为８５次ｍｏｄ３加法，比同类的算法都快。此外，这里给出的算法结构简单，易于实现。     

DECODING ALGORITHM BASED QN REVISED SYNDROME FOR THE BINARY (23,12,7) GOLAY CODE

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.     

Decoding algorithm based on revised syndrome for the binary (23,12,7) Golay code

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     

Recursive triangular array ladder algorithms

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     

Cyclotomic FFTs With Reduced Additive Complexities Based on a Novel Common Subexpression Elimination Algorithm

In this paper, we first propose a novel common subexpression elimination (CSE) algorithm for matrix-vector multiplications over characteristic-2 fields. As opposed to previously proposed CSE algorithms, which usually focus on complexity savings due to recurrences of subexpressions, our CSE algorithm achieves two types of complexity reductions, differential savings and recurrence savings, by taking advantage of the cancelation property of characteristic-2 fields. Using our CSE algorithm, we reduce the additive complexities of cyclotomic fast Fourier transforms (CFFTs). Using a weighted sum of the numbers of multiplications and additions as a metric, our CFFTs achieve smaller total complexities than previously proposed CFFTs and other FFTs, requiring both fewer multiplications and fewer additions in many cases.      

IRA码最小和译码算法的改进算法

研究了重复累积(IRA)码的简化译码算法.IRA码的BP译码算法具有较高的复杂度,为了降低复杂度,首先提出将最小和算法应用于IRA码.然而,最小和算法使译码性能降低约1.2 dB.为了在复杂度和译码复杂度之间取得较好的折衷,提出了对IRA码的最小和算法的改进算法:归一化算法和偏移算法.仿真结果表明,IRA码归一化算法和偏移算法在复杂度略有增加的情况下,性能得到明显改善.     

Frame Synchronization Algorithm for LDPC Coded Burst Systems

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.     

A VLSI architecture for simplified arithmetic Fourier transformalgorithm

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     

一种用于RaptorQ码的降维快速译码算法

针对新型高效数字喷泉码RaptorQ码译码复杂度高的问题,利用它是系统码的特性,该文提出一种降维快速译码算法。该算法利用预先计算的逆矩阵,将译码过程中对接收编码约束矩阵的求逆转化为对更小维数矩阵的求逆,以降低译码复杂度。算法译码效果与现有译码算法等价。仿真结果表明,在信道符号删除概率较低(小于0.2)时,该算法的译码速度显著高于现有算法。     

Decoding algorithms for noncoherent trellis coded modulation

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     

A bounded-distance decoding algorithm for the Leech lattice, withgeneralizations

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     

Simple MAP decoding of first-order Reed-Muller and Hamming codes

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.     

Fair and efficient scheduling for UMTS forward link

This paper presents two scheduling algorithms, MWF²Q+ 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 MWF²Q+ 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.     

低重分配概率的OVSF码重分配算法

在采用正交可变长扩频因子(OVSF)码作为信道化码的直接序列扩频码分多址系统中,提出用重分配概率作为重分配算法的一个新的评价指标,重分配概率越小,系统的计算复杂度越低。进而提出一种低重分配概率的、基于空码容量的重分配算法,在解决本次码阻塞的同时,兼顾对未来高数据速率的呼叫的支持能力,减少未来码阻塞发生。仿真证实,重分配概率比已有2种重分配算法都小。     

改进的离散字母表迭代译码算法研究

为了优化LDPC迭代译码性能和降低算法复杂度,提出了一种改进的基于Gallager A算法的2b离散字母表迭代译码算法。在每一轮迭代中,Tanner图上的校验节点与变量节点之间所传递的消息有1b表示符号值,另1b反映码字结构特性,其中变量节点更新规则是通过查表法来实现的。在二元对称信道下针对列重为3的规则LDPC码做了仿真实验,仿真结果表明该算法性能明显优于原算法,并且具有较低的复杂度。     

PPM performance with BWT complexity: a fast and effective datacompression algorithm

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(n²) 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     

Fast technique for computing syndromes of B.C.H. and Reed-Solomon codes

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.     

二维离散余弦变换的一种新的快速算法

本文介绍了二维离散余弦变换(DCT)的一种新的快速算法。对于NN DCT(N=2m),只需用N个一维DCT和若干加法运算。与常规的行-列法相比,所需的乘法运算量减少了一半,也比其它的快速算法的乘法运算量要少,而加法运算量基本上是相同的。     

低信噪比下归零Turbo码码长及其帧同步识别

针对目前高斯消元法在归零Turbo码长、帧同步等参数识别过程存在容错性能低且计算复杂度高的缺点,该文提出一种低信噪比(SNR)下基于差分似然差(DLD)的识别算法。首先通过定义差分似然差的概念,利用归零Turbo码帧头两码元差分似然差为正值(“+”)的特性,构建分析矩阵实现码长的识别;其次,提出基于最小错误判决准则下的差分似然差“+”位置门限判决方法,完成帧同步;最后,从工程实际出发,遍历寄存器个数的可能值,实现码率、寄存器个数以及交织长度识别。仿真实验表明：所提算法对于归零Turbo码码长、帧同步等参数识别有效,差分似然差“+”位置分布与分析的数据结构特征一致,判决门限能够有效判断差分似然差“+”位置,同时,算法容错性能较强,在信噪比为–5 dB条件下,码长、帧同步等参数识别率能够达到90%以上,并且算法的复杂度远小于现有算法。     

协作通信中一种分布式酉空时码

提出了一种基于三角函数酉星座的分布式酉空时码,主要介绍了编码矩阵结构及其低复杂度的译码算法。根据仿真结果可知:提出的酉空时性能差于正交设计、系统设计和循环酉群码的性能,但从译码复杂度看,所提出的译码算法计算复杂度相比其他3种简单很多,具有很大的优势。并且还证明了同样的码字采用最大似然译码算法与所提出的低复杂度算法性能相近,但是计算复杂度相差较大。总的来说,所提出的编码矩阵结构简单,易于构造,且具有较低的译码复杂度。