基于MEA算法的RS(255,223)码的译码软件实现

遵循有限域上多项式的运算规则,使用MATLAB软件设计了GF(28)上的加法、乘法、求逆运算模块,并以这些模块为基础,采用修正的欧几里德算法(MEA)与有限域上快速傅立叶变换算法相结合的思想,实现了RS(255,223)的软件译码。此软件参数可调,可以适应GF(2n)域(n≤8)上不同本原多项式、不同纠错能力的RS码,具有很强的通用性。仿真结果表明,所设计的RS(255,223)译码软件运行效率高,满足实时通信传输需要;并为算法开发、验证和硬件设计调试提供了一种强有力的辅助手段。     

A note on the decoding complexity of error-correcting codes

A time-space tradeoff lower bound for the decoding complexity of asymptotically good error-correcting codes for oblivious write-k-times branching programs is proved. Specifically, we prove that the computation time T and space S of every oblivious write-k-times branching program that decodes an asymptotically good error-correcting code with block length n satisfy S⋅Tk=Ω((n/k)^k+1).     

一种低复杂度的LDPC码改进型UMP BP-Based译码算法*

为了弥补UMP BP-Based相对于LLR BP译码算法的性能缺陷,提出一种改进型UMP BP-Based译码算法。通过将Normalized BP-Based和Offset BP-Based译码算法的优点相结合,并利用最小均方误差准则来计算该算法中的参数。仿真结果表明,在相同误码率的情况下,改进型UMP BP-Based译码算法比UMP BP-Based、Normalized BP-Based以及Offset BP-Based具有更好的LDPC译码性能。     

A parallel Viterbi decoding algorithm

In this paper we express the Viterbi algorithm as a matrix–vector reduction in which multiplication is replaced by addition and addition by minimization. The resulting algorithm is then readily parallelized in a form suitable for implementation on a systolic processor array. We describe the algorithm for Bose–Chaudhuri–Hocquenghem (BCH) codes which have a task graph with its valence restricted to four inputs and four outputs. The method is also applicable to convolution codes, but the complexity of the task graph increases with the number of input bits for these codes. Results for BCH codes are given for two general purpose parallel machines, an IBM SP2 and a Meiko CS2. Copyright © 2001 John Wiley & Sons, Ltd.     

基于改进型UMP BP-Based算法的LDPC译码研究

为了弥补UMP BP-Based译码算法相对于LLR BP译码算法的性能缺陷,提出一种改进型UMP BP-Based译码算法.该算法中的参数是在最小均方误差准则下确定的,对所有的LDPC码的译码具有通用性.仿真结果表明,在相同误码率的情况下,改进型UMP BP-Based译码算法比UMP BP-Based译码算法、Normalized BP-Based译码算法以及Offset BP-Based译码算法具有更好的LDPC译码性能.     

高数据吞吐率Reed-Solomon解码器

提出了一种新型的高数据吞吐率RS解码器,它采用无除法Berlekamp Massey,Chien和Forney等算法实现。该解码器采用一种新型的结构化复接流水线结构,具有很高的效率和突出的吞吐能力。根据设计实现的解码器性能,该解码器相比现有的解码器具有显著的吞吐率增益。     

里德索罗门码数据库水印的研究

在结合现有的各种水印算法的基础上,提出了一种基于交叉里德索罗门码的数字水印方法,其主要思想是：在整体上利用大数选举对水印进行差错控制,在局部引入交叉里德索罗门码对水印信息进行纠错编码,使得水印信息对随机性和突发性错误具有很强的纠错能力。理论分析和实验结果表明,该算法对数据库影响很小,隐蔽性好,在提高水印鲁棒性的同时增加了数据库的水印可嵌入量,具有很好的应用价值。     

一种改进的LT码置信传播译码

在删除信道上,短信息字长度的LT码采用置信传播译码算法性能较差。提出了一种改进的置信传播译码算法,此算法在置信传播译码失败时只需运用高斯消元法确定少数猜测比特就可实现成功译码。仿真结果显示,相比于置信传播译码,改进的置信传播译码算法在增加少量译码运行时间的代价下获得较大的译码性能改善。     

List decoding of Hermitian codes using Gröbner bases

List decoding of Hermitian codes is reformulated to yield an efficient and simple algorithm for the interpolation step. The algorithm is developed using the theory of Gröbner bases of modules. The computational complexity of the algorithm seems comparable to previously known algorithms achieving the same task, and the algorithm is better suited for hardware implementation.     

A fixed-parameter tractable algorithm for matrix domination

Matrix domination is the NP-complete problem of determining whether a given {0,1} matrix contains a set of k non-zero entries that are in the same row or same column as all other non-zero entries. Using a kernelization and search tree approach, we show the problem to be fixed-parameter tractable with running time .     

吉比特里所码和卷积码级联译码器设计

针对60-GHz无线个域网,提出了一种吉比特里所码和卷积码级联译码器架构。在推荐级联架构中,里所码和卷积码分别作为外码和内码,通过交织器级联。采用基于Viterbi算法的8路并行卷积译码结构和基于RiBM算法的里所码译码结构,实现了超高速级联译码器。在TSMC 0.13μm CMOS工艺下,该译码器以0.135 nJ/bit和5.19 mm2的能耗资源开销实现了高达2 Gb/s的吞吐率。     

一种改进的LLR-SPA译码新算法

针对LDPC码目前广泛使用的译码算法精度低的问题,在LLR-SPA译码算法的基础上提出了一种提高译码精度的新算法。该算法将LLR-SPA算法中复杂度较高的雅可比修正项采用泰勒级数进行分段线性近似,实验表明,该算法在译码复杂度基本不变的情况下,可以大幅度地提高其译码精度。     

A nondeterministic space-time tradeoff for linear codes

We are interested in proving exponential lower bounds on the size of nondeterministic D-way branching programs computing functions in linear time, that is, in time at most kn for a constant k. Ajtai has proved such lower bounds for explicit functions over domains D of size about n, and Beame, Saks and Thathachar for functions over domains of size about k²². We prove an exponential lower bound ²Ω(n/ck) for an explicit function over substantially smaller domain D of size about k². Our function is a universal function of linear codes.     

LDPC码在LTE-Advanced中的应用及编译码算法研究

通过分析LTE-Advanced系统中LDPC码的校验矩阵构造方法,找到了与LTE兼容的低码率扩展方法,针对该扩展方法提出了两种优化的编码算法,并在MATLAB平台的仿真测试环境下,通过最小和译码算法进行译码。测试结果表明,LDPC码非常适合用于高速传输系统中,仿真对比得到的最优修正值使译码性能得到改善,能满足高精度的数字信号传输需要。为LTE-Advanced系统的信道编解码器的硬件设计提供了一套有效的编译码算法方案,具有较好的实用价值。     

List decoding codes on Garcia–Stictenoth tower using Gröbner basis

An account of the interpolation and the root-finding steps of list decoding of one-point codes is given. The interpolation step is reduced to the problem of finding the minimal element of the Gröbner basis of a submodule of a free module over a polynomial ring of one variable. The procedure for root-finding of the interpolation polynomial going modulo a large degree place is described from the tower point of view.     

Reed-Solomon时域编、译码算法与AVR优化实现

Reed-Solomon纠错码是一种最佳的近似正交码,AVR高速嵌入式单片机功能强大,在无线数据传输应用方面很有优势。该文从时域的角度出发引入了Reed-Solomon码的时域编码及译码改进算法,并结合AVR高速嵌入式单片机Atmega128的特点对算法进行了优化。该算法可以在较短的时间,占用较少存贮器的条件下实现Reed-Solomon的编码和译码操作。     

广义LDPC码的自适应全并行MAP-BP译码算法

提出了一种广义LDPC码的自适应全并行MAP-BP译码算法,算法中子码采用基于比特栅格的最大后验概率译码,本地码采用基于对数似然比的置信传播译码。算法引入自适应修正因子保证迭代过程中子码和本地码输出信息的匹配。仿真结果表明,与传统广义LDPC译码算法相比,MAP-BP算法可提高译码准确性并能加快译码收敛速度。     

基于改进的分层译码算法的QC-LDPC译码器设计

对空间数据系统委员会(CCSDS)推荐的QC-LDPC码进行了研究,给出了改进的分层译码算法.基于改进的分层译码算法设计部分并行结构QC-LDPC译码器,译码速率较快,适合应用需求,并通过仿真验证所设计的译码器的性能.