On the distribution of computation for sequential decoding using the stack algorithm

An analytical procedure is presented for generating the computational distribution for the Zigangirov-Jelinek stack algorithm. Multitype branching processes are employed to develop a procedure for estimating sequential decoding computation, without the need for simulation, but with sufficient accuracy to be a valid design tool. At information rates about the cutoff rateR_{o}the calculated computational performance is virtually Identical to that obtained by time consuming simulations.     

一种CABAC解码引擎的芯片实现

CABAC(Context-based Adaptive Binary Arithmetic coding)是H.264中所采用的一种高效熵编码,压缩率高,但结构复杂,硬件实现难度大。本文在P.Zhang 2008年的工作[1]基础上提出一种单周期CABAC解码引擎的优化实现方法,通过查表替换、分支预测、逻辑调整、反相器优化等关键路径优化方法和寄存器精简等面积优化方法进一步提高了解码性能。经过芯片验证,CABAC解码引擎性能提高到250Mbps,面积减少46%,峰值工作情形下功耗1.03mW,满足下一代视频编解码协议(QFHD)的需求。     

A unified framework for tree search decoding: rediscovering the sequential decoder

We consider receiver design for coded transmission over linear Gaussian channels. We restrict ourselves to the class of lattice codes and formulate the joint detection and decoding problem as a closest lattice point search (CLPS). Here, a tree search framework for solving the CLPS is adopted. In our framework, the CLPS algorithm is decomposed into the preprocessing and tree search stages. The role of the preprocessing stage is to expose the tree structure in a form matched to the search stage. We argue that the forward and feedback (matrix) filters of the minimum mean-square error decision feedback equalizer (MMSE-DFE) are instrumental for solving the joint detection and decoding problem in a single search stage. It is further shown that MMSE-DFE filtering allows for solving underdetermined linear systems and using lattice reduction methods to diminish complexity, at the expense of a marginal performance loss. For the search stage, we present a generic method, based on the branch and bound (BB) algorithm, and show that it encompasses all existing sphere decoders as special cases. The proposed generic algorithm further allows for an interesting classification of tree search decoders, sheds more light on the structural properties of all known sphere decoders, and inspires the design of more efficient decoders. In particular, an efficient decoding algorithm that resembles the well-known Fano sequential decoder is identified. The excellent performance-complexity tradeoff achieved by the proposed MMSE-DFE Fano decoder is established via simulation results and analytical arguments in several multiple-input multiple-output (MIMO) and intersymbol interference (ISI) scenarios.     

FPGA design and implementation of a low-power systolic array-based adaptive Viterbi decoder

In this paper, by modifying the well-known Viterbi algorithm, an adaptive Viterbi algorithm that is based on strongly connected trellis decoding is proposed. Using this algorithm, the design and a field-programmable gate array implementation of a low-power adaptive Viterbi decoder with a constraint length of 9 and a code rate of 1/2 is presented. In this design, a novel systolic array-based architecture with time multiplexing and arithmetic pipelining for implementing the proposed algorithm is used. It is shown that the proposed algorithm can reduce by up to 70% the average number of ACS computations over that by using the nonadaptive Viterbi algorithm, without degradation in the error performance. This results in lowering the switching activities of the logic cells, with a consequent reduction in the dynamic power. Further, it is shown that the total power consumption in the implementation of the proposed algorithm can be reduced by up to 43% compared to that in the implementation of the nonadaptive Viterbi algorithm, with a negligible increase in the hardware.     

An integrated interpolative PCM decoder

Discusses the technique of time averaging interpolation which provides a means for obtaining telephone quality digital-to-analog conversion using conventional digital integrated-circuit processing. Describes a monolithic circuit that decodes the 8-kHz companded PCM commonly used in voiceband communication systems. The circuit, realized in a standard buried collector bipolar technology, contains 300 integrated injection logic (I/SUP 2/L) gates together with a current-driven resistive ladder network. The performance of the decoder exceeds typical toll network objectives.     

An asynchronous instruction length decoder

This paper describes an investigation of potential advantages and pitfalls of applying an asynchronous design methodology to an advanced microprocessor architecture. A prototype complex instruction set length decoding and steering unit was implemented using self-timed circuits. [The Revolving Asynchronous Pentium^(R) Processor Instruction Decoder (RAPPID) design implemented the complete Pentium II^(R) 32-bit MMX instruction set.] The prototype chip was fabricated on a 0.25 μm CMOS process and tested successfully. Results show significant advantages - in particular, performance of 2.5-4.5 instructions per nanosecond - with manageable risks using this design technology. The prototype achieves three times the throughput and half the latency, dissipating only half the power and requiring about the same area as the fastest commercial 400 MHz clocked circuit fabricated on the same process     

An artificial neural net Viterbi decoder

The Viterbi algorithm is a maximum likelihood means for decoding convolutional codes and has thus played an important role in applications ranging from satellite communications to cellular telephony. In the past, Viterbi decoders have usually been implemented using digital circuits. The speed of these digital decoders is directly related to the amount of parallelism in the design. As the constraint length of the code increases, parallelism becomes problematic due to the complexity of the decoder. In this paper an artificial neural network (ANN) Viterbi decoder is presented. The ANN decoder is significantly faster than comparable digital-only designs due to its fully parallel architecture. The fully parallel structure is obtained by implementing most of the Viterbi algorithm using analog neurons as opposed to digital circuits. Several modifications to the ANN decoder are considered, including an analog/digital hybrid design that results in an extremely fast and efficient decoder. The ANN decoder requires one-sixth the number of transistors required by the digital decoder. The connection weights of the ANN decoder are either +1 or -1, so weight considerations in the implementation are eliminated. This, together with the design's modularity and local connectivity, makes the ANN Viterbi decoder a natural fit for VLSI implementation. Simulation results are provided to show that the performance of the ANN decoder matches that of an ideal Viterbi decoder     

An area-saving decoder structure for ROMs

Read-only memories (ROMs) are widely used in both digital communication systems and daily consumer electronics. The major functions of ROMs are storage of data, programs, firmwares, etc. In this paper, a three-dimensional decoding structure for ROMs is proposed. The number of address decoding stages is drastically shortened. Hence, the delay is reduced, as well as the power consumption and area. The analysis of overall transistor count and delay is thoroughly derived. A real 256 /spl times/ 8 ROM possessing the proposed decoder is physically fabricated by 0.5-/spl mu/m two-poly two-metal (2P2M) CMOS technology.     

Use of a sequential decoder to analyze convolutional code structure (Corresp.)

An existing sequential decoding program can be easily modified to enumerate the number of low-weight codewords in a convolutional code, where weight is defined either over a decoding constraint length or "free." We tabulated several good rate one-half constraint-length 49 systematic codes that were obtained quickly with this procedure.     

A sequential soft-decision decoder for Reed-Solomon codes appliedto encoded PSK in Rayleigh-fading channels

A soft-decision stack algorithm with a variable-bias-term branch metric and accurate channel state information estimate is applied to a Reed-Solomon-encoded phase-shift keying (PSK) system in the presence of memoryless Rayleigh fading. To compensate for the variable decoding delay inherent in sequential decoding algorithms, a time-out mechanism is used by the inner decoder: if a time-out occurs before complete decoding of a given block, the decoder declares an erasure. An erasures-and-errors correction decoding algorithm is implemented at the outer decoder to recover any incorrect or incompletely decoded inner code words. Simulation results show that significant improvement over uncoded modulation can be achieved with this approach with moderate cost in decoding complexity     

A fast multispeed comma-free Reed-Solomon decoder for W-CDMA applications using foldable systolic array architecture

This brief proposes a fast multispeed comma-free Reed-Solomon (CFRS) decoder for the frame synchronization and code-group identification in the cell search of the Third Generation Partnership Project wide-band code-division multiple access/frequency division duplexing (W-CDMA/FDD) system. A foldable systolic array is proposed to achieve fast decoding and provide flexible tradeoffs between power consumption, chip size, and decoding latency. Multispeed decoding, an idea that is useful for cell search in different application scenarios, can also be achieved with the same array architecture. The proposed CFRS decoder is implemented in a 3.3-V 0.35-/spl mu/m CMOS technology with 2.2 /spl times/ 2.2 mm/sup 2/ core area and power dissipation of 13.3 and 1.23 mW in high- and low-speed decoding modes, respectively.     

一种兼容Turbo码的LDPC解码器

提出了一种兼容Turbo码的低密度校验码(LDPC)解码器,它可以将Turbo码完全转化为LDPC码来进行解码,由于采用了校验分裂方法来处理由Turbo码转化而来的LDPC码中所存在的短环,从而使其解码性能优于联合校验置信度传递(JCBP)算法0.8 dB,仅仅比Turbo码专用的BCJR算法损失约为1dB.本文提出的通用解码器,为多系统兼容通信设备的应用提供了一种新的、灵活方便的实现途径.     

An RCJL decoder for a Josephson memory

A resistor-coupled Josephson logic (RCJL) [1] decoder was proposed and experimentally tested to satisfy the requirements for a Josephson cache memory. The RCJL decoder is an ac powered latch decoder and is constructed from RCJL AND-OR units. Therefore, it has advantages in regard to higher packing density, reduced decoding time, and intrinsically damped resonance phenomena over interferometer decoders. A 4-bit decoder, consisting of 28 AND-OR units, was fabricated using a 4-µm Pb-alloy technology. A ±14- percent gate-bias-current margin was obtained.     

An effective simplifying scheme for Viterbi decoder

A Viterbi decoding algorithm with a scarce-state transition-type circuit configuration, namely the probability selecting states (PSS) mode decoder, is presented. The algorithm has reduced complexity compared to a conventional Viterbi decoder. It is shown that this method has three advantages over the general Viterbi algorithm: it is suitable to the quick look-in code, it applies the optimum decoding in a PSS-type decoder, and it makes full use of the likelihood concentration property. The bit-error-rate (BER) performance of a r=1/2, k=7 (147,135) code and PSS-type Viterbi decoder approximates the optimum performance of the standard Viterbi decoder and reduces the hardware of the conventional Viterbi decoder to about half     

An iterative multiuser decoder for near-capacity communications

The combination of forward error correction (FEC) coding and random interleaving is shown to overcome the limitations of multiuser detectors/decoders when the user cross correlations are high. In particular, one can asymptotically achieve single-user performance in a highly correlated multiuser system. In addition, an optimal iterative multiuser detector is derived from iterative techniques for cross-entropy minimization. A practical suboptimal implementation of this algorithm is presented, and simulations demonstrate that, even with highly correlated users, it achieves optimal asymptotic efficiency. The effects of the theoretical limits on channel capacity are evident in many of the simulation results. The complexity of the suboptimal algorithm is approximately (O(2^K)+O(2^κ)) per bit per iteration where K is the number of users and κ is the code constraint length     

An efficient Chase decoder for turbo product codes

In this letter, we propose an efficient decoding algorithm for turbo product codes as introduced by Pyndiah. The proposed decoder has no performance degradation and reduces the complexity of the original decoder by an order of magnitude. We concentrate on extended Bose-Chaudhuri-Hocquengem codes as the constituent row and column codes because of their already low implementation complexity. For these component codes, we observe that the weight and reliability factors can be fixed, and that there is no need for normalization. Furthermore, as opposed to previous efficient decoders, the newly proposed decoder naturally scales with a test-pattern parameter p that can change as a function of iteration number, i.e., the efficient Chase algorithm presented here uses conventionally ordered test patterns, and the syndromes, even parities, and extrinsic metrics are obtained with a minimum number of operations.     

An optimal circular Viterbi decoder for the bounded distance criterion

We propose a Viterbi-type decoder for tailbiting trellis codes that works by traversing the tailbiting circle somewhat more than once. The traversal is the least possible for any bounded distance Viterbi decoder. Procedures are given that compute this minimum. Unlike previous decoders of the type, the new scheme does not suffer limit cycles or from pseudocodewords. The bit-error rate is compared to that of Bahl-Cocke-Jelinek-Raviv and maximum-likelihood decoding.     

An overview of median and stack filtering

Within the last two decades a small group of researchers has built a useful, nontrivial theory of nonlinear signal processing around the median-related filters known as rank-order filters, order-statistic filters, weighted median filters, and stack filters. This required significant effort to overcome the bias, both in education and research, toward linear theory, which has been dominant since the days of Fourier, Laplace, and Convolute.We trace the development of this theory of nonlinear filtering from its beginnings in the study of noise-removal properties and structural behavior of the median filter to the recently developed theory of optimal stack filtering.The theory of stack filtering provides a point of view which unifies many different filter classes, including morphological filters, so it is discussed in detail. Of particular importance is the way this theory has brought together, in a single analytical framework, both the estimation-based and the structural-based approaches to the design of these filters.Some recent applications of median and stack filters are provided to demonstrate the effectiveness of this approach to nonlinear filtering. They include: the design of an optimal stack filter for image restoration; the use of vector median filters to attenuate impulsive noise in color images and to eliminate cross luminance and cross color in TV images; and the use of median-based filters for image sequence coding, reconstruction, and scan rate conversion in normal TV and HDTV systems.     

Parallel and sequential block Kalman filtering and theirimplementations using systolic arrays

Two sets of block Kalman filtering equations that differ in the manner of generating the initial and updated estimates are derived. Parallel and sequential schemes for generating these estimates are adopted. It is shown that the parallel implementation inherently leads to a block Kalman estimator which provides filtered estimates at the vector (block) level and fixed-lag smoother estimates at the sample level. The sequential implementation scheme, on the other hand, generates the estimates of each sample recursively, leading naturally to a scalar (filter) estimator. These scalar estimates are arranged in a vector form, resulting in a block estimator which solely generates filtered estimates both at the vector and sample levels. Simulation results on a speech signal are presented which indicate the advantages of the sequential block Kalman filter. An algorithm for iterative calculation of Kalman gain and error covariance matrices is given which does not require any matrix inversion operation. The implementation of this algorithm using available systolic array processors is presented. A ring systolic array which can be used to implement the state update part of the block Kalman filter is suggested     

GCC编译器中的堆栈保护技术概述

以堆栈溢出为代表的缓冲区溢出已经成为最为普遍的安全漏洞之一。自从1988年缓冲区漏洞被发现以来,虽然经过几十年的努力,科研人员提出了各种防护方法,但是在操作系统或者软件当中总有新的溢出漏洞或者其变种被发现。为了尽可能避免堆栈溢出漏洞被攻击者利用,一直以来,众多的编译器工作者在GCC编译器中尝试了多种方法来保护内存中的堆栈区域。