While long polar codes can achieve the capacity of arbitrary binary-input discrete memoryless channels when decoded by a low complexity successive-cancellation (SC) algorithm, the error performance of the SC algorithm is inferior for polar codes with finite block lengths. The cyclic redundancy check (CRC)-aided SC list (SCL) decoding algorithm has better error performance than the SC algorithm. However, current CRC-aided SCL decoders still suffer from long decoding latency and limited throughput. In this paper, a reduced latency list decoding (RLLD) algorithm for polar codes is proposed. Our RLLD algorithm performs the list decoding on a binary tree, whose leaves correspond to the bits of a polar code. In existing SCL decoding algorithms, all the nodes in the tree are traversed, and all possibilities of the information bits are considered. Instead, our RLLD algorithm visits much fewer nodes in the tree and considers fewer possibilities of the information bits. When configured properly, our RLLD algorithm significantly reduces the decoding latency and, hence, improves throughput, while introducing little performance degradation. Based on our RLLD algorithm, we also propose a high throughput list decoder architecture, which is suitable for larger block lengths due to its scalable partial sum computation unit. Our decoder architecture has been implemented for different block lengths and list sizes using the TSMC 90-nm CMOS technology. The implementation results demonstrate that our decoders achieve significant latency reduction and area efficiency improvement compared with the other list polar decoders in the literature.

There has been renewed interest in decoding Reed-Solomon (RS) codes without using syndromes recently. In this paper, we investigate the complexity of syndromeless decoding, and compare it to that of syndrome-based decoding. Aiming to provide guidelines to practical applications, our complexity analysis focuses on RS codes over characteristic-2 fields, for which some multiplicative FFT techniques are not applicable. Due to moderate block lengths of RS codes in practice, our analysis is complete, without big notation. In addition to fast implementation using additive FFT techniques, we also consider direct implementation, which is still relevant for RS codes with moderate lengths. For high-rate RS codes, when compared to syndrome-based decoding algorithms, not only syndromeless decoding algorithms require more field operations regardless of implementation, but also decoder architectures based on their direct implementations have higher hardware costs and lower throughput. We also derive tighter bounds on the complexities of fast polynomial multiplications based on Cantor's approach and the fast extended Euclidean algorithm.

When polar codes are decoded by the successive cancellation (SC) decoding algorithm, erroneously decoded non-frozen bits are caused by either channel noise or error propagation. SC-Flip algorithms aim to improve error performance by first identifying erroneous hard decisions due to channel noise and then flipping them during the decoding process to reduce error propagation. In existing SC-Flip algorithms, cyclic redundancy check (CRC) is used to check the decoded codeword to detect incorrect hard decisions. Differing from this detection approach based on CRC, we propose new SC-Flip decoders that take advantage of both the CRC and distributed parity checks (PCs) to detect, identify and flip erroneously decoded non-frozen bits. The proposed decoders terminate SC decoding early when a distributed PC is not satisfied. In addition, we propose a new metric to help locate the incorrect hard decisions. Finally, simulation results demonstrate that our SC-Flip decoders achieve better performance complexity tradeoffs than prior flipping algorithms, and approach the performance and complexity of the SC-Oracle algorithms.

In this paper, we investigate geometrical properties of the rank metric space and covering properties of rank metric codes. We first establish an analytical expression for the intersection of two balls with rank radii, and then derive an upper bound on the volume of the union of multiple balls with rank radii. Using these geometrical properties, we derive both upper and lower bounds on the minimum cardinality of a code with a given rank covering radius. The geometrical properties and bounds proposed in this paper are significant to the design, decoding, and performance analysis of rank metric codes.

In this paper, we reduce the computational complexities of partial and dual partial cyclotomic FFTs (CFFTs), which are discrete Fourier transforms where spectral and temporal components are constrained, based on their properties as well as a common subexpression elimination algorithm. Our partial CFFTs achieve smaller computational complexities than previously proposed partial CFFTs. Utilizing our CFFTs in both transform- and time-domain Reed-Solomon decoders, we achieve significant complexity reductions.