分组码的格图结构和译码

本文讨论了分组码的格图结构,给出了某些BCH码L段格图结构,并据此提出了BCH码的快速最大似然译码算法,同时讨论了qm元分组码的q元映象的译码问题,给出了q元映象的直和划分结构和相应的译码算法。     

Algebraic properties of BCH codes useful for decoding

In this paper theorems are presented which allow the simplified decoding of (n, k, δ) BCH codes in certain cases of practical interest. Such results are in a way implicit in the theory of BCH codes, but so far have not appeared explicitly in the literature. It is shown that any t₀ errors, 1 ? t₀ ? δ-1, can be detected by using any set of only t₀ consecutive coefficients of the syndrome polynomial. The correction of any t₀ errors, 1 ? t₀ ? [(δ-1)/2], can be performed by using any set of 2t₀ consecutive coefficients of the syndrome polynomial, where [x] means the integer part of x. Similar results are derived for punctured BCH codes. In this case sets of t₀ or 2t₀ consecutive coefficients, respectively, for detecting or correcting t₀ errors, are selected from the δ-1-p higher-order coefficients of the modified syndrome polynomial, where p is the number of digits punctured from a code word. These results hold true even when the punctured digits are not consecutive.     

ON THE DECODING OF ALGEBRAIC GEOMETRIC CODES BASED ON FIA

Suppose C is an irreducible algebraic curve of genus g, C*(D,G) is an algebraic geometric code with designed minimum distance d* = deg(G)-2g 2. In this paper, a decoding algorithm based on Fundamental Iterative Algorithm(FIA) is presented, also its reasonableness is proved. In fact, our decoding algorithm is a modification of the algorithm proposed by G. L. Fend and T. R. N. Rao(1993) and can correct any received words with errors not more than (d*-1)/2, whereas the complexity is only about one half as much as Feng and Rao's. The procedure can be implemented easily by hardware or software.     

Reduced-complexity decoding algorithms for unitary space-time codes

Two reduced-complexity decoding algorithms for unitary space-time codes based on tree-structured constellation are presented. In this letter original unitary space-time constellation is divided into several groups. Each one is treated as the leaf nodes set of a subtree. Choosing the unitary signals that represent each group as the roots of these subtrees generates a tree-structured constellation. The proposed tree search decoder decides to which sub tree the receive signal belongs by searching in the set of subtree roots. The final decision is made after a local search in the leaf nodes set of the selected sub tree. The adjacent subtree joint decoder performs joint search in the selected sub tree and its ＂surrounding＂ subtrees, which improves the Bit Error Rate （BER） performance of purely tree search method. The exhaustively search in the whole constellation is avoided in our proposed decoding algorithms, a lower complexity is obtained compared to that of Maximum Likelihood （ML） decoding. Simulation results have also been provided to demonstrate the feasibility of these new methods.     

Research on encoding and decoding of non-binary polar codes over GF(2m)

Binary Polar Codes (BPCs) have advantages of high-efficiency and capacity-achieving but suffer from large latency due to the Successive-Cancellation List (SCL) decoding. Non-Binary Polar Codes (NBPCs) have been investigated to obtain the performance gains and reduce latency under the implementation of parallel architectures for multi-bit decoding. However, most of the existing works only focus on the Reed-Solomon matrix-based NBPCs and the probability domain-based non-binary polar decoding, which lack flexible structure and have a large computation amount in the decoding process, while little attention has been paid to general non-binary kernel-based NBPCs and Log-Likelihood Ratio (LLR) based decoding methods. In this paper, we consider a scheme of NBPCs with a general structure over GF(2^m). Specifically, we pursue a detailed Monte-Carlo simulation implementation to determine the construction for proposed NBPCs. For non-binary polar decoding, an SCL decoding based on LLRs is proposed for NBPCs, which can be implemented with non-binary kernels of arbitrary size. Moreover, we propose a Perfect Polarization-Based SCL (PPB-SCL) algorithm based on LLRs to reduce decoding complexity by deriving a new update function of path metric for NBPCs and eliminating the path splitting process at perfect polarized (i.e., highly reliable) positions. Simulation results show that the bit error rate of the proposed NBPCs significantly outperforms that of BPCs. In addition, the proposed PPB-SCL decoding obtains about a 40% complexity reduction of SCL decoding for NBPCs.     

一种适用于DTMB系统的NR译码方法

在分析国标数字电视传输系统NR编码的基础上,提出一种以节省硬件资源为目标的NR译码方法。首先根据DTMB系统中(16,8,6)NR编码关系式,推导出由衍生比特表示信息比特的生成关系式;进而,结合信息比特表示衍生比特的生成关系式、衍生比特表示信息比特的生成关系式和(16,8,6)NR码至多可以纠正2位误码的特点,通过逻辑分析,给出了NR译码方法;然后,根据译码方法,设计了硬件实现结构;最后,通过实例分析了本文方法的译码过程及可行性,并分析了硬件实现资源情况。本文方法能够达到(16,8,6)NR码纠2位误码的纠错极限,与传统的最大似然估计算法相比,实现简单,极大降低了译码器的复杂度,节省了硬件资源。     

Trellis decoding of Reed-Solomon codes in low bit rate speechcommunications

The residual redundancy that persists in the transmitted parameters of a low bit rate speech coder are exploited to reduce the computational complexity of a Reed-Solomon (RS) trellis decoder. The use of RS codes for mobile telephony provides the opportunity for avoiding channel interleaving and so reduces one-way delay     

无线信道中网格编码调制技术研究

网格编码调制技术（TCM）是一种将编码与调制有机结合起来的技术,可使系统的频带利用率和功率资源同时得到有效利用。在对TCM原理和结构分析的基础上,研究了网格编码调制技术中的几个关键技术,主要包括集分割原理和无线信道下TCM误码率的分析,最后对无编码的QPSK与8PSK—TCM进行了仿真比较。仿真结果表明,在无线信道相同的误码率下,采用网格编码调制技术比未编码QPSK获得2dB的编码增益。     

Suboptimum decoding of decomposable block codes

To decode a long block code with a large minimum distance by maximum likelihood decoding is practically impossible because the decoding complexity is simply enormous. However, if a code can be decomposed into constituent codes with smaller dimensions and simpler structure, it is possible to devise a practical and yet efficient scheme to decode the code. This paper investigates a class of decomposable codes, their distance and structural properties. It is shown that this class includes several classes of well-known and efficient codes as subclasses. Several methods for constructing decomposable codes or decomposing codes are presented. A two-stage (soft-decision or hard-decision) decoding scheme for decomposable codes, their translates or unions of translates is devised, and its error performance is analyzed for an AWGN channel. The two-stage soft-decision decoding is suboptimum. Error performances of some specific decomposable codes based on the proposed two-stage soft-decision decoding are evaluated. It is shown that the proposed two-stage suboptimum decoding scheme provides an excellent trade-off between the error performance and decoding complexity for codes of moderate and long block length     

A* decoding of block codes

The A* algorithm is applied to maximum-likelihood soft-decision decoding of binary linear block codes. This paper gives a tutorial on the A* algorithm, compares the decoding complexity with that of exhaustive search and Viterbi decoding algorithms, and presents performance curves obtained for several codes     

一种改进的Turbo乘积码译码算法

针对Turbo乘积码(TPC)译码复杂度高、运算量大的缺点,分析了一种改进的TPC译码算法。该算法以Chase迭代算法为基础,通过对错误图样重新排序产生新的测试序列,其伴随式可从前次伴随式的基础上修正一位得到,大大简化了计算步骤。在AWGN信道下对新算法进行了Matlab仿真,结果表明,改进的算法在保持译码性能基本不变的前提下,提高了译码速度,降低了译码复杂度。     

Near-optimum decoding of product codes: block turbo codes

This paper describes an iterative decoding algorithm for any product code built using linear block codes. It is based on soft-input/soft-output decoders for decoding the component codes so that near-optimum performance is obtained at each iteration. This soft-input/soft-output decoder is a Chase decoder which delivers soft outputs instead of binary decisions. The soft output of the decoder is an estimation of the log-likelihood ratio (LLR) of the binary decisions given by the Chase decoder. The theoretical justifications of this algorithm are developed and the method used for computing the soft output is fully described. The iterative decoding of product codes is also known as the block turbo code (BTC) because the concept is quite similar to turbo codes based on iterative decoding of concatenated recursive convolutional codes. The performance of different Bose-Chaudhuri-Hocquenghem (BCH)-BTCs are given for the Gaussian and the Rayleigh channel. Performance on the Gaussian channel indicates that data transmission at 0.8 dB of Shannon's limit or more than 98% (R/C>0.98) of channel capacity can be achieved with high-code-rate BTC using only four iterations. For the Rayleigh channel, the slope of the bit-error rate (BER) curve is as steep as for the Gaussian channel without using channel state information     

BEAST decoding of block codes obtained via convolutional codes

BEAST is a bidirectional efficient algorithm for searching trees. In this correspondence, BEAST is extended to maximum-likelihood (ML) decoding of block codes obtained via convolutional codes. First it is shown by simulations that the decoding complexity of BEAST is significantly less than that of the Viterbi algorithm. Then asymptotic upper bounds on the BEAST decoding complexity for three important ensembles of codes are derived. They verify BEAST's high efficiency compared to other algorithms. For high rates, the new asymptotic bound for the best ensemble is in fact better than previously known bounds.     

Method of soft-decision decoding of block codes

A method of soft-decision decoding of a block code was considered as a solution of the problem of estimating “soft” values of information symbols by the maximum-likelihood method. Estimation of values of information symbols was conducted under conditions where levels of continuous output signals of a discriminator (demodulator) were subjected to an appropriate interpretation with due regard for the coding rule.     

Performance of sphere decoding of block codes

A sphere decoder searches for the closest lattice point within a certain search radius. The search radius provides a tradeoff between performance and complexity. We focus on analyzing the performance of sphere decoding of linear block codes. We analyze the performance of soft-decision sphere decoding on AWGN channels and a variety of modulation schemes. A hard-decision sphere decoder is a bounded distance decoder with the corresponding decoding radius. We analyze the performance of hard-decision sphere decoding on binary and q-ary symmetric channels. An upper bound on the performance of maximum-likelihood decoding of linear codes defined over F_q (e.g. Reed- Solomon codes) and transmitted over q-ary symmetric channels is derived and used in the analysis.We then discuss sphere decoding of general block codes or lattices with arbitrary modulation schemes. The tradeoff between the performance and complexity of a sphere decoder is then discussed.     

Iterative decoding of binary block and convolutional codes

Iterative decoding of two-dimensional systematic convolutional codes has been termed “turbo” (de)coding. Using log-likelihood algebra, we show that any decoder can be used which accepts soft inputs-including a priori values-and delivers soft outputs that can be split into three terms: the soft channel and a priori inputs, and the extrinsic value. The extrinsic value is used as an a priori value for the next iteration. Decoding algorithms in the log-likelihood domain are given not only for convolutional codes but also for any linear binary systematic block code. The iteration is controlled by a stop criterion derived from cross entropy, which results in a minimal number of iterations. Optimal and suboptimal decoders with reduced complexity are presented. Simulation results show that very simple component codes are sufficient, block codes are appropriate for high rates and convolutional codes for lower rates less than 2/3. Any combination of block and convolutional component codes is possible. Several interleaving techniques are described. At a bit error rate (BER) of 10^-4 the performance is slightly above or around the bounds given by the cutoff rate for reasonably simple block/convolutional component codes, interleaver sizes less than 1000 and for three to six iterations     

Universally optimum block codes and convolutional codes with maximum likelihood decoding

A new proof is presented for the existence of block codes whose error probability under maximum likelihood decoding is bounded asymptotically by the random coding bound universally over all discrete memoryless channels. On the basis of this result, the existence of convolutional codes with universally optimum performance is shown. Furthermore the existence of block codes which attain the expurgated bound universally over all discrete memoryless channels is proved under the use of maximum likelihood decoding.     

几类格的快速译码

本文通过研究16维Barnes-Wall格和基于构造A的二元线性分组码、四元线性分组码的导出格的代数结构,将这些格的译码问题转化为在相应码的格图上求最短路径的问题,从而提出了这些格的快速译码算法,并分析了译码算法的时间复杂性。     

Distributed decoding of cyclic block codes using a generalizationof majority-logic decoding

One-step majority-logic decoding is one of the simplest algorithms for decoding cyclic block codes. However, it is an effective decoding scheme for very few codes. This paper presents a generalization based on the “common-symbol decoding problem.” Suppose one is given M (possibly corrupted) codewords from M (possibly different) codes over the same field; suppose further that the codewords share a single symbol in common. The common-symbol decoding problem is that of estimating the symbol in the common position. This is equivalent to one-step majority logic decoding when each of the “constituent” codes is a simple parity check. This paper formulates conditions under which this decoding is possible and presents a simple algorithm that accomplishes the same. When applied to decoding cyclic block codes, this technique yields a decoder structure ideal for parallel implementation. Furthermore, this approach frequently results in a decoder capable of correcting more errors than one-step majority-logic decoding. To demonstrate the simplicity of the resulting decoders, an example is presented     

衰落信道下的格形码设计

衰落信道下ＴＣＭ好码的设计准则是使有效码长度最长，同时使其对应路径的欧几里德距离乘积最大。本文首先从理论上得到有效码长度与卷积编码器的状态数，并行输入数之间的关系。提出了一种能达到最大自由长的状态转移图－标准拓扑篱笆图的概念，在此基础上，对衰落信道下采用速率为（２／３）８ＰＳＫ信号集合时的ＴＣＭ好码进行搜索，与文献中已有码相比，利用准则判别和进行蒙特－卡洛模拟都说明了新码在抗衰落方面的良好性能。