# Coarsely Quantized Decoding and Construction of Polar Codes Using the Information Bottleneck Method
## 1 Introduction  
In a typical transmission chain, forward error correction is a resource-hungry and computationally complex component. Therefore, it is always desirable to reduce the decoder's complexity. The commonly used soft decision decoders perform many intensive arithmetic operations on soft values, i.e., log-likelihood ratios (LLRs). In practice, the computational complexity of a decoder is reduced by replacing the intensive operations with simpler approximations. The space complexity of the decoder, i.e., the memory for storing the soft values and the number of wires for exchanging them between hardware components, depends on the representation of the soft values in the hardware. The space complexity of the decoder is reduced by coarsely quantizing the soft values where each soft value is represented using a small number of bits. These complexity reduction measures degrade the error-correcting performance of a decoder to some extent. An interesting remedy for reducing the decoder complexity of low-density parity-check (LDPC) codes was presented in [1; 2], where a quantized decoder for regular LDPC codes was developed using the information bottleneck method [3; 4]. The design principle of such a quantized decoder combines the information bottleneck method with discrete density evolution [5]. Discrete density evolution isthe quantized counterpart of density evolution [6], an analysis tool for LDPC codes. In the quantized decoder design of [1], referred to as the _information bottleneck_ decoder here, the information bottleneck method is used to design mappings between the quantized input and output messages of each node in the Tanner graph of the code which maximize the mutual information between the outgoing messages and the bits they correspond to. Consequently, all the node operations in the information bottleneck decoder are deterministic mappings that can be realized as simple table lookups. Further, the decoder can be implemented using only unsigned integer arithmetic since all the quantized messages are unsigned integers. Moreover, no internal high resolution is needed for the node operations. Surprisingly, the computational simplicity of the information bottleneck decoders causes only a minute degradation in the error rate as compared to a double-precision floating-point sum-product decoder. It was reported that an information bottleneck decoder having a bitwidth as low as 4 bits performs very close to the belief propagation decoder [1]. The idea of information bottleneck decoders was extended to irregular LDPC codes in [7; 8]. Design of quantized message passing decoders that utilize information preserving table lookup operations was also addressed in [9; 10; 11; 12]. Results of [1; 2; 7; 12] encourage to explore the application of the information bottleneck method in polar codes [13], an important class of channel codes that are seen as a breakthrough in the coding theory. They are the first linear block codes that can provably achieve the symmetric capacity of binary input memoryless channels. Despite being asymptotically good, the error correcting performance of polar codes at practical block lengths under successive cancellation (SC) [13] decoding is not impressive. This ordinary performance of polar codes was partly due to their weak Hamming distance properties [14; 15] and partly due to the SC decoder being suboptimal [16]. To circumvent these issues, the authors in [16] proposed a serial concatenation of the polar code with an outer cyclic redundancy check (CRC) code and the use of the successive cancellation list (SCL) decoder. On the one hand, the SCL decoder is more powerful than the originally proposed SC decoder. On the other hand, the outer CRC code improves the distance properties of the polar code as observed in [17]. The resulting CRC-aid successive cancellation list decoding scheme can outperform state-of-the-art coding schemes. The outer CRC code can also be replaced with generalized parity check codes [18], resulting in parity check aided SCL decoding.