Polar codes are the latest breakthrough in coding theory, as they are the first family of codes with explicit construction that provably achieve the symmetric capacity of binary-input discrete memoryless channels. Polar encoding and successive cancellation decoding have the complexities of N log N , for code length N. Although, the complexity bound of N log N is asymptotically favorable, we report in this work methods to further reduce the encoding and decoding complexities of polar coding. The crux is to relax the polarization of certain bit-channels without performance degradation. We consider schemes for relaxing the polarization of both very good and very bad bit-channels, in the process of channel polarization. Relaxed polar codes are proved to preserve the capacity achieving property of polar codes. Analytical bounds on the asymptotic and finite-length complexity reduction attainable by relaxed polarization are derived. For binary erasure channels, we show that the computation complexity can be reduced by a factor of six, while preserving the rate and error performance. We also show that relaxed polar codes can be decoded with significantly reduced latency. For additive white Gaussian noise channels with medium code lengths, we show that relaxed polar codes can have lower error probabilities than conventional polar codes, while having reduced encoding and decoding computation complexities.

Arıkan's polar codes are proven to be capacity-achieving error correcting codes while having explicit constructions. They are characterized to have encoding and decoding complexities of l log l, for code length l. In this work, we construct another family of capacity-achieving codes that have even lower encoding and decoding complexities, by relaxing the channel polarizations for certain bit-channels. We consider schemes for relaxing the polarization of both sufficiently good and sufficiently bad bit-channels, in the process of channel polarization. We prove that, similar to conventional polar codes, relaxed polar codes also achieve the capacity of binary memoryless symmetric channels. We analyze the complexity reductions achievable by relaxed polarization for asymptotic and finite-length codes, both numerically and analytically. We show that relaxed polar codes can have better bit error probabilities than conventional polar codes, while having reduced encoding and decoding complexities.

This paper describes the architecture and implementation of a constraint-length 14 Viterbi decoder that achieves a decoding rate of 41 Kbits/s. The system uses 36 Xilinx XC4010 FPGAs with seven processor cards and a custom backplane to implement a multi-ring general cascade Viterbi decoder architecture. The paper also shows how to achieve decoding rates of 1 Mbit/s using current FPGA technology. Comparisons are made to JPL's big Viterbi decoder, which uses custom ASICs.

This paper presents some recent advances in the architecture for the data compression technique known as arithmetic coding. The new architecture employs loop unrolling and speculative execution of the inner loop of the algorithm to achieve a significant speed-up relative to the Q-coder architecture. This approach reduces the number of iterations required to compress a block of data by a factor that is on the order of the compression ratio. While the speed-up technique has been previously discovered independently by researchers at IBM, no systematic study of the architectural trade-offs has ever been published. For the CCITT facsimile documents, the new architecture achieves a speed-up of approximately seven compared to the IBM Q-coder when four lookahead units are employed in parallel. A structure for fast input/output processing based on run length pre-coding of the data stream to accompany the new architecture is also presented.>

Two new algorithms for performing arithmetic coding without multiplication are presented. The first algorithm, suitable for an alphabet of arbitrary size, reduces the worst-case normalized excess length to under 0.8% versus 1.911% for the previously known best method of Chevion et al. The second algorithm, suitable only for alphabets of less than twelve symbols, allows even greater reduction in the excess code length. For the important binary alphabet the worst-case excess code length is reduced to less than 0.1% versus 1.1% for the method of Chevion et al. The implementation requirements of the proposed new algorithms are discussed and shown to be similar.>

In a Viterbi decoder, there are two known memory organization techniques for the storage of survivor sequences from which the decoded information sequence is retrieved, namely, register exchange method and traceback method. This work extends previously known traceback approaches, describes two new traceback algorithms, and compares various traceback methods with each other. Memory size, latency, and implementational complexity of the survivor sequence management are analyzed for both uniprocessor and multiprocessor realizations of Viterbi decoders. A new, one-pointer traceback method is shown to be better than previously known traceback methods.>

A family of multiprocessor architectures implementing the Viterbi algorithm is presented. The family of architectures is shown to be capable of achieving an increase in throughput which is directly proportional to the number of processors when the number of processors is smaller than the constraint length of the code v. The hardware utilization of nearly 100% and availability of deep pipelining inside each processor are demonstrated. An implementation proposal for a constraint length v=14 Viterbi decoder based on the proposed family of architectures is presented. The proposed thirteen-processor decoder is intended to be compatible with specifications for the Galileo space probe being developed by the Jet Propulsion Laboratory.>