Area-efficient reed-solomon decoder design for optical communications

A high-speed low-complexity Reed-Solomon (RS) decoder architecture based on the recursive degree computationless modified Euclidean (rDCME) algorithm is presented in this brief. The proposed architecture has very low hardware complexity compared with the conventional modified Euclidean and degree computationless modified Euclidean (DCME) architectures, since it can reduce the degree computation circuitry and replace the conventional systolic architecture that uses many processing elements (PEs) with a recursive architecture using a single PE. A high-throughput data rate is also facilitated by employing a pipelining technique. The proposed rDCME architecture has been designed and implemented using SMIC 0.18-mum CMOS technology. Synthesized results show that the proposed RS (255, 239) decoder requires only about 18 K gates and can operate at 640 MHz to achieve a throughput of 5.1 Gb/s, which meets the requirement of modern high-speed optical communications.     

Iterative decoder architectures

Implementation constraints on iterative decoders applying message-passing algorithms are investigated. Serial implementations similar to traditional microprocessor datapaths are compared against architectures with multiple processing elements that exploit the inherent parallelism in the decoding algorithm. Turbo codes and low-density parity check codes, in particular, are evaluated in terms of their suitability for VLSI implementation in addition to their bit error rate performance as a function of signal-to-noise ratio. It is necessary to consider efficient realizations of iterative decoders when area, power, and throughput of the decoding implementation are constrained by practical design issues of communications receivers.     

Area-efficient architectures for the Viterbi algorithm II.Applications

In part I the theoretical foundations of a new class of area-efficient architectures for the Viterbi algorithm were established. Area-efficient architectures for practical codes are presented here to illustrate the design procedures and demonstrate the favourable area-time tradeoff results. Three examples from convolutional codes, matched-spectral-null (MSN) trellis codes, and Ungerboeck codes are presented. The application of the area-efficient techniques to codes with a very large number of states, codes with time-varying trellises, and a programmable Viterbi decoder is discussed     

Area-efficient architectures for the Viterbi algorithm. I. Theory

In the state-parallel implementation of the Viterbi algorithm, one add-compare-select (ACS) unit is devoted to each state in the treillis. A systematic approach to partitioning, scheduling, and mapping N trellis states to P ACSs, where N>P , is presented here. The area saving of this architecture comes from the reduced number of ACSs and interconnection wires. The design of the ACS, path metric storage, and routing network is discussed in detail. The proposed architecture creates internal parallelism due to the ACS sharing, which can be exploited to increase the throughput rate by pipelining. Consequently, the architecture offers a favorable (smaller) area-time product, compared to the state-parallel implementation     

改进型高吞吐率QC-LDPC码解码器设计

通过对LDPC码解码算法及解码器结构的研究,本文提出一种改进型高吞吐率QC-LDPC码解码器设计方案.综合考虑硬件复杂度和解码吞吐率,该方案利用分层解码算法和部分并行结构进行设计,并采用提前检测技术,消除冗余的迭代,实现高吞吐率.然后通过ModelSim SE6.0对该解码器进行仿真测试,验证了其功能的正确性,最后采用...     

Area-efficient analog decoder design for low density parity check codes in deep-space applications

Area-efficient design methodology is proposed for the analog decoding implementations of the rate-½ accumulate repeat-4 jagged-accumulate (AR4JA) low density parity check (LDPC) code. The proposed approach is designed using optimized decoding architecture and regularized routing network, in such a way that the overall wiring overhead is minimized and the silicon area utilization is significantly improved. The prototyping chip used to verify the approach is fully integrated in a four-metal double-poly 0.35 μm complementary metal oxide semiconductor (CMOS) technology, and includes an input-output interface that maximizes the decoder throughput. The decoding core area is 2.02 mm² with a post-layout area utilization of 80%. The decoder was successfully tested at the maximum data rate of 10 Mbit/s, with a core power consumption of 6.78 mW at 3.3 V, which corresponds to an energy per decoded bit of 0.677 nJ. The proposed analog LDPC decoder with low processing power and high-reliability is suitable for space- and power-constrained spacecraft system.     

Mapping interleaving laws to parallel turbo decoder architectures

For high data rate applications, the implementation of iterative turbo-like decoders requires the use of parallel architectures posing some collision-free constraints to the reading/writing process in the soft-input soft-output (SISO) decoders. Contrary to the literature belief, we prove in this paper that the parallelism constraints can be met by any permutation law employed by the turbo-interleaver, and we give a constructive method to satisfy those constraints.     

Variable-size interleaver design for parallel turbo decoder architectures

In this paper, we propose two techniques to design good S-random interleavers, to be used in parallel and serially concatenated codes with interleavers. The interleavers designed according to these algorithms can be shortened, in order to support different block lengths in such a way that all the permutations obtained by pruning, when employed in a parallel turbo decoder, are collision-free. The first technique, suitable for short and medium interleavers, guarantees the same performance of nonparallel interleavers in terms of spreading properties, simulated frame-error probabilities, and obtainable minimum distance of the actual codes. The second algorithm, to be used for large block lengths, permits achieving high degrees of parallelism at the price of a slight degradation of the spread properties, and also to change the degree of parallelism on-the-fly. The operations of a parallel turbo decoder employing these interleavers are described, and an example of the advantages of the proposed techniques is provided in a realistic system framework.     

Memory optimization of MAP turbo decoder algorithms

Turbo codes are the most recent breakthrough in coding theory. However, the decoder's implementation cost limits their incorporation in commercial systems. Although the decoding algorithm is highly data dominated, no true memory optimization study has been performed yet. We have extensively and systematically investigated different memory optimizations for the maximum a posteriori (MAP) class of decoding algorithms. It turns out that it is not possible to present one decoder structure as being optimal. In fact, there are several tradeoffs, which depend on the specific turbo code, the implementation target (hardware or software), and the selected cost function. We therefore end up with a parametric family of new optimized algorithms out of which the designer can choose. The impact of our optimizations is illustrated by a representative example, which shows a significant decrease in both decoding energy (factor 2.5) and delay (factor 1.7)     

一种新颖的Turbo码MAP译码器

根据Turbo码trellis结束的情况及Turbo码的特征本文提出了一种新的Turbo码MAP译码器。这是基于MAP译码器中两个组成译码器性能的不一致所作改进,从分析和仿真结果我们可以看到该方法的优势。     

VLSI architectures for the MAP algorithm

This paper presents several techniques for the very large-scale integration (VLSI) implementation of the maximum a posteriori (MAP) algorithm. In general, knowledge about the implementation of the Viterbi (1967) algorithm can be applied to the MAP algorithm. Bounds are derived for the dynamic range of the state metrics which enable the designer to optimize the word length. The computational kernel of the algorithm is the add-MAX* operation, which is the add-compare-select operation of the Viterbi algorithm with an added offset. We show that the critical path of the algorithm can be reduced if the add-MAX* operation is reordered into an offset-add-compare-select operation by adjusting the location of registers. A general scheduling for the MAP algorithm is presented which gives the tradeoffs between computational complexity, latency, and memory size. Some of these architectures eliminate the need for RAM blocks with unusual form factors or can replace the RAM with registers. These architectures are suited to VLSI implementation of turbo decoders.     

Parallel high-throughput limited search trellis decoder VLSI design

Limited search trellis decoding algorithms have great potentials of realizing low power due to their largely reduced computational complexity compared with the widely used Viterbi algorithm. However, because of the lack of operational parallelism and regularity in their original formulations, the limited search decoding algorithms have been traditionally ruled out for applications demanding very high throughput. We believe that, through appropriate algorithm and hardware architecture co-design, certain limited search trellis decoding algorithms can become serious competitors to the Viterbi algorithm for high-throughout applications. Focusing on the well-known T-algorithm, this paper presents techniques at the algorithm and VLSI architecture levels to design fully parallel T-algorithm limited search trellis decoders. We first develop a modified T-algorithm, called SPEC-T, to improve the algorithmic parallelism. Then, based on the conventional state-parallel register exchange Viterbi decoder, we develop a parallel SPEC-T decoder architecture that can effectively transform the reduced computational complexity at the algorithm level to the reduced switching activities in the hardware. We demonstrate the effectiveness of the SPEC-T design solution in the context of convolutional code decoding. Compared with state-parallel register exchange Viterbi decoders, the SPEC-T convolutional code decoders can achieve almost the same throughput and decoding performance, while realizing up to 56% power savings. For the first time, this work provides an approach to exploit the low power potential of the T-algorithm in very high throughput applications.     

MAP译码器的免归一化处理信息更新算法

在不改变译码性能的条件下,为了加快最大后验概率(Maximum A Posteriori Probability,MAP)译码器状态信息更新的速度和降低算法的复杂度,提出了一种用于Turbo码的MAP译码器的免归一化处理算法.算法采用二进制补码加法器和减法器将MAP译码过程中的状态信息投影到一个归一化圆上,当状态信息更新时所有的状态信息在归一化圆上移动,通过保持归一化圆上状态信息的正确关系来计算似然比.归一化过程中不用搜索或估计状态信息的最大值,通过简化状态信息归一化过程加速了MAP译码器的状态信息更新并降低了复杂度.所提算法在与传统算法译码性能相同的情况下,可以降低36.2％的计算复杂度和17.4％的关键路径延迟,达到MAP译码器实现中的高速、低复杂度目标.     

Low-latency architectures for high-throughput rate Viterbi decoders

In this paper, a novel K-nested layered look-ahead method and its corresponding architecture, which combine K-trellis steps into one trellis step (where K is the encoder constraint length), are proposed for implementing low-latency high-throughput rate Viterbi decoders. The proposed method guarantees parallel paths between any two-trellis states in the look-ahead trellises and distributes the add-compare-select (ACS) computations to all trellis layers. It leads to regular and simple architecture for the Viterbi decoding algorithm. The look-ahead ACS computation latency of the proposed method increases logarithmically with respect to the look-ahead step (M) divided by the encoder constraint length (K) as opposed to linearly as in prior work. For a 4-state (i.e., K=3) convolutional code, the decoding latency of the Viterbi decoder using proposed method is reduced by 84%, at the expense of about 22% increase in hardware complexity, compared with conventional M-step look-ahead method with M=48 (where M is also the level of parallelism). The main advantage of our proposed design is that it has the least latency among all known look-ahead Viterbi decoders for a given level of parallelism.     

Mapping interleaving laws to parallel turbo and LDPC decoder architectures

For high-data-rate applications, the implementation of iterative turbo-like decoders requires the use of parallel architectures posing some collision-free constraints to the reading/writing process from/into the memory. This consideration applies to the two main classes of turbo-like codes, i.e., turbo codes and low-density parity-check (LDPC) codes. Contrary to the literature belief, we prove in this paper that there is no need for an ad hoc code design to meet the parallelism requirement, because, for any code and any choice of the scheduling of the reading/writing operations, there is a suitable mapping of the variables in the memory that grants a collision-free access. The proof is constructive, i.e., it gives an algorithm that obtains the desired collision-free mapping. The algorithm is applied to two simple examples, one for turbo codes and one for LDPC codes, to illustrate how the algorithm works.     

MAP译码器嵌入式状态信息存储机制设计

嵌入式状态信息存储机制(ESMS)是一种用于turbo码的MAP译码算法以减少其状态信息对存储器容量需求的方法。对于LOG_MAP译码器,本文提出的ESMS从前向和后向状态信息更新过程中各取一个嵌入式状态信息,并用更新后的状态信息减掉嵌入式状态信息,从而减少对存储器的需求和计算复杂度。在状态信息更新过程中不保存的嵌入式状态的似然比信息通过网格中各状态的相对关系来保持。这样,嵌入式状态信息不用存储,且与用嵌入式状态信息相关的计算也可以省略。嵌入式状态存储机制可以使MAP译码器VLSI实现过程中减小面积和时延。     

Implementation and performance of a turbo/MAP decoder

The implementation and performance of a turbo/MAP decoder are described. A serial block MAP decoder operating in the logarithm domain is used to obtain a very-high-performance turbo decoder. Programmable gate arrays and EPROMs allow the decoder to be programmed for almost any code from four to 512 states, rate 1/3 to rate 1/7 (higher rates are achieved with puncturing) and interleaver block sizes to 65,536 bits. Seven decoding stages were implemented in parallel. For rate 1/3 and 1/7 16-state codes with an interleaver size of 65,536 bits and operating at up to 356 kbit/s the codec achieved an E_b/N₀ of 0⋅32 and −0⋅30 dB respectively for a BER of 10⁻⁵. BERs down to 10⁻⁷ were also achieved for a small increase in E_b/N₀. An efficient implementation of a continuous MAP decoder is also presented, along with a synchronization technique for turbo decoders. © 1998 John Wiley & Sons, Ltd.     

高存储效率的MAP译码器网格信息更新实现方法

本文提出一种新型的高存储效率的最大似然译码(MAP)译码器网格信息更新实现方法,该方法可以降低Turbo码译码器状态阵列计算对存储器的需求.利用该实现方法可以使得MAP译码器的前向网格信息和后向网格信息共享同一存储器,而且前向和后向的网格信息更新以及MAP译码产生的外部信息同时进行计算;因此该法可以提高Turbo译码的运算速度、降低存储器开销,进而降低Turbo译码电路实现时的硅片面积.     

一种新型的turbo码LOG-MAP译码算法

给出了一种新型的turbo码LOC-MAP译码算法，相对于传统的LOG-MAP译码算法，主要有两点创新。其一，对于LOC-MAP算法中的校正函数采用三阶Newton插值函数拟合，相对于分段线性函数拟合，省去了查找表过程和查找表的存储；其二，相对于传统的单滑动窗口技术，采用双滑动窗口技术，对于前向递归和后向递归分别采用滑动窗口技术，同时采用预处理技术，这样显著地提高了译码速度。     

基于DSP处理器的UMTS Turbo MAP解码器高效实现

Turbo码自1993年问世以来,以其出色的性能,在工业和科研领域都引起了广泛的关注.Turbo码性能逼近(信噪比差为0.7dB或更小)由Claude E.Shannon确定的信道容限.