The polar code is one of the error correcting codes which was proposed by Dr. Arıkan It attracts the attention of researchers due to the capacity achieving algorithms over a wide range of channels. However polar codes sacrifices encoding complexity and latency to improve error performance. To address this issue, wave pipelining is proposed in this article. The main advantage of pipelining is parallelism which leads to the improvement in latency. In addition, the system gets the benefit of the increased computation rate, or throughput. The absence of registers at the intermediate stages in the wave pipeline makes the polar code more power efficient and efficient area overheads. It provides a method for significantly reducing clock by keeping the external functionality and timing of any circuit. This architecture is coded in VHDL language and the design is synthesized in SYNOPSYS tool and implemented in the Virtex-7 VC 709 FPGA device. The synthesis report proved that 50 % of efficiency in area and timing in the wave pipelining compared to the conventional methods.
Research Article
An efficient implementation of novel Polar encoder with Wavelet pipelining Architecture for 5G Networks
https://doi.org/10.21203/rs.3.rs-2234670/v1
This work is licensed under a CC BY 4.0 License
You are reading this latest preprint version
Polar codes
Encoder
Wave pipelining
VHDL
FPGA
Binary Memoryless Symmetric (BMS) channel otherwise known as Polar Codes [1] has a low-end complexity in terms of encoding and decoding. Perfect bit or noisy bit channels in a N channel polar code approaching infinity is based on the polarization phenomena of merging and splitting the channels thus assembling perfect bit channels of capacity I symmetric to the channels W. The channel W being an independent channel which is also a Binary Memoryless Symmetric channel, polarization happens on merging and splitting thereby transmitting data in the form of polar codes. This transmission is made possible through perfect bit channels that also promotes in working towards fixing frozen bits in channels that are completely noisy. According to Shannon’s coding theorem, several studies have worked together in achieving a noiseless channel transmission. Lately, on comparison with existing coding techniques, an advanced method to construct codes namely channel polarization was proposed [1–4], which aided to attain a symmetrical capacity of BDMC (Binary to Discrete Memoryless Channel) specifically BSC(p). Another study [5] has deconstructed the polar codes in BSC. [6–7] has characterized bounds and exponents in the construction of BSC for polar codes [8] has proposed a decoder based on LP (Linear Programming) that simulates differentiated decoders to hand out a SC (Successive Cancellation) Decoder and BEC at the same time. Bakshi et.al [9] has proposed a study to merge a concatenated RS(Reed – Solomon) code that uses inner codes and outer codes simultaneously. Polar codes are built to pick particular bit channels from N bits in [1] to [9] studies. Monte –Carlo Algorithms simulate complex channels [1] iteratively. [2] and [3] studies proposed that Polar codes work towards convoluting function but its metrics are not precise enough on complex calculations. Telatar et.al [4] has put forward approximation of bit channel with Nµ log 2 µ, where the user defined parameter, µ controls the output at an approximation stage. GA (Gaussian Approximation) uses Additive White Gaussian Noise (AWGN) to build polar codes in those channels proposed in [5–7]. Building Polar Codes on the basis of Polarization Weight (PW) does approximation of bit channels independently suggested by [8] and [9]. Code rates and code lengths need to be arbitrary which is achieved by the codes that are shortened and punctured are put forward in [10] to [17]. Puncturing procedure is performed channel independently [10] to set a stopping point with the minimum bit value. These punctured bits are also known as decoders.[11] has proposed another puncturing algorithm which known as QUP (Quasi Uniform Puncturing) to puncture the bits that are in the reverse order from the initial value to P (P is the total number which indicates the number of bits to be punctured). Re-ordering mechanism followed by puncturing is suggested in [12] which makes use of GA methodology that punctures bits from positions that are frozen. Tal et.al [13] has used RCPP which optimizes the code family with unalike code rates. These conventional codes use the frozen bits that are all zero thus increasing the performance of decoders. Methodology to shorten the polar codes are suggested by [14] and [15] which generates the weights along the column of the matrices. A unique method that
shortens the polar code is suggested in [16] which also punctured by a less complex construction method. An optimized algorithm with a pattern to shorten polar codes with a set of frozen codes is put forward in [17]. Nevertheless the pattern of the channels on being punctured and shortened, it is mandatory for re-arranging the channel bits based on the operations performed. Re-ordering mechanisms through GA is performed in AWGN channels so as to puncture the bits that are coded or shorten the bits that are coded. Selected codes that are nevermore in the underlying channel W undergoes puncturing and shortening that are parallel to the underlying channel. Original channel differ from the bit channel built from the underlying channel without undergoing the process of being punctured and shortened. Re-arranging of these bit channels helps to avoid performance distortion. Anyhow, GA is only pertinent to be used in AWGN channels. Advanced measures need to be performed to shorten the polar codes or to puncture the polar codes which is one inspiration that this article provides. Punctured or shortened coded bits aid in the building of polar codes, by considering the underlying channels to generalize the issue in which the BMS channels need to be independent regardless of the identical ones. The symmetric nature of polar codes proven in [1] vary the underlying channel in the new environment provided. The relationship based on Tal–Vardy’s algorithm is found to degrade when operated in such environment. By analyzing a modified version Tal–Vardy’s algorithm [4] theoretically, the new environment becomes applicable for BMS channel that rearranges the bits in the underlying channels that could be unconstrained or different. Efficient FPGA Implementation of Chaotic based Communication System with Polar Encoding is proposed in [18]. In this article the parallel processing is discussed and the author claimed the latency reduction. Based on the theoretical analysis, a modification to the Tal–Vardy algorithm [4] that is applicable to any BMS channel is proposed to reorder the bit channels when the underlying channels are independent BMS channels (which, again, could be different channels).
The rest of this paper is organized as follows. In Section 2, we briefly introduce the basics Encoding of polar codes. The general construction of Wave pipelining encoder procedure is presented in Section 3. The coding is done in VHDL language and the discussion of result is presented in Section 4 and this article ends with concluding remarks which is given in Section 5.
2.1 Encoding of Polar code
Polar codes are unique in the way they split the channel as good and bad channels, (during the encoding the polar code make the channel as reliable and unreliable) and the message bits are transmitted only through the induced good(reliable) channels, while the information to the unreliable channels are almost frozen.
Let the length of the codeword is N, the messages are transmitted into k reliable channels then and (N − k) channels are unreliable and they are set to 0 as they are not useful for message transmission. This N-k bits are called frozen bits.
Let W be a binary discrete memoryless channel (B-DMC) with u and x are the input and output respectively. When two bits (u1, u2) are transmitted, two values (x1, x2) are received (as shown in Fig. 1). The general equation for encoder for 2-bit value is given in (1).
\({x}_{1}^{2}= {u}_{1}^{2} {G}_{2}\) . -----------------------------------------------------------------------(1)
Where G2 is the generator matrix and its value is
$$\left(\genfrac{}{}{0pt}{}{1 0}{1 1}\right)$$
For encoding 2-bit value (Fig. 1)using the above notation we obtain(2).
x1 = (u1 ⊕ u2) and x2 = u2 ---------------------------------------------------(2)
Similarly for encoding N = 4 bits (Fig. 2) we need to use the matrix G4. We obtain (3)
\({\text{x}}_{1}^{4}= {\text{u}}_{1}^{4}{\text{G}}_{4}\) -----------------------------------------------------------------(3)
In this case we have x1 = (u1⊕u2⊕u3⊕u4), x2 = (u3⊕u4), x3 = (u2⊕u4) and x4 = u4. In the same way we can obtain ‘n’ bit value encoder.
To encode more bits, this kind of process may sacrifice complexity and latency. That may not be desirable for a high-speed data network like 5G.
3.1 Wave Pipelining
A fundamental and well explored concept used in the design of digital systems is pipelining. Pipelining is a popular hardware design technique that takes advantage of parallelism. The key benefit of utilizing a pipeline design is the increased computation rate, or throughput, available. For a computational task, throughput is typically increased by reducing the time at which it takes to complete said task. Pipelining increases throughput by increasing the number of tasks that can be executed in parallel and therefore increasing the number of tasks that can be computed concurrently, otherwise known as increasing bandwidth.
The throughput of a pipelined system is determined by the maximum rate at which the pipeline can operate. In this model, the maximum clock rate is limited by the maximum path delay difference across a combinational logic rather than the maximum path delay. Six stage pipeline is explained in Fig. 4 there are 6, tasks processing concurrently in this design. The latency for each task is 6 clock cycles, but as previously explained, the latency between outputs is only 1 clock cycle.
3.2 Wave Pipeline Design for Polar Code
A maximum-rate pipeline is not achievable using conventional pipelining so only wave pipleining is proposed in this article. However, by removing the intermediate registers within a pipeline, a wave pipeline becomes a close realization of a maximum-rate pipeline. Wave pipelining in Polar encoder can reduce the clock load of a circuit as well as the associated area and power while maintaining the timing of the circuit. Another difference between conventional and wave pipelines is the relationship between clock rate and path delay. In the conventional 4 bit encoding method the system uses 10 intermediate registers. Obviously 10 clock cycle were required to move the inputs to the output. Where as in the wave pipelining method the number of tasks (xor operation) are executed in parallel (computed concurrently). Thus, minimum number of clock cycles are expected here for a wave to propagate through the wave pipeline before being latched by the output register. In addition, by removing intermediate registers in this process wave pipelining reduced the clock load of a circuit as well as the associated area and power while maintaining the timing of the circuit.
In this proposed research work, the architectural design of Wave pipeline Polar codes is implemented using Xilinx 9.2i ISE and Model Sim 6.3. The program was written in VHDL coding and the encoded output is shown Fig 5. The WP – Polar architecture is also synthesized in both Xilinx and Synopsys tools. The above implementation provides us a detailed analysis on area and power consumptions. WP – Polar reduces the area overheads and reduced power dissipation due to the absence of intermediate registers.
In the conventional 4 bit encoding method (Fig 6) the system uses 10 intermediate registers. Obviously 10 clock cycle were required to move the inputs to the output. In the wave pipelining method the number of tasks (xor operation) were executed in parallel (computed concurrently). Thus, minimum number of clock cycles were expected here for a wave to propagate through the wave pipeline before being latched by the output register(fig 7).
Due to absence of the intermediate register and pipeline stages the reduce in the static and dynamic power hence SoC power gets reduced. Here latency is calculated by the time taken by any encoder design to generate its output after the clock signal is applied. Table 1 provides the device utilization summary of two, three stage and Wave pipelining is given. As the stages of pipe-line increases, the incremental gate count and number of flip flops also increases due to the intermediate registers. Gate count and flip flops have increased from 794 in 2-stage pipeline to 1702 in 3-stage pipeline. where as it has been observed that there is a significant reduction in number of flip flops and gate count used for wave pipelining. As the table showcase, efficient utilization of equivalent gate count and the number of slices is achieved by wave pipelined architecture with a count of 302 and 12 respectively. The gate count increases with the increase in the number of pipeline stages because of the insertion of additional registers.
Table 1: Device Utilization summary(area)
The bar chart (Fig. 8) is plotted considering device utilization without pipeline and with different pipeline stages.
The summary of timing analysis is given in Table 2. Here the timing analysis is based on the maximum time required by the output calculated in nanoseconds (ns). The time required by the two stages and three stage encoders is 4.89 ns and 4.04 ns respectively. The time required by the wave pipelined architecture is 3.939 ns. In normal pipelining stages, intermediate data are stored in registers, whereas in wave pipelining the data are handled by delays.
Table 2: Summary of Timing Analysis
The architecture of wave pipelining was synthesized using Synopsys where utilization of area and power was obtained. Fig 9 indicates the cell area utilization of pipe-lined and wave pipelined architecture.
Due to the absence of intermediate registers in the pipelined stages, Cell area utilized by wave pipelined Polar encoder is much lesser compared to other pipelined architectures. Fig 10 shows the cell area utilization of (8,4) Polar Encoder, where the area is measured in μm2 . The total cell area occupied by normal design, two stage, three stage and wave pipelining are 43,660.715 μm2 The below chart showcases the power Utilization of different pipelined architecture of Polar encoder. Analysis is made using Synopsys tool which is measured in milliwatt (mW) (Fig. 10).
The power utilized by normal design, two stage and three stage pipelines are 4.125 mW, 5.05 mW and 5.9 mW respectively, which is effectively reduced by using wave pipelined structure and the power utilized is 3.8 mW. Field-Programmable Gate Array (FPGAs) is explicitly intended to address the issues of high volume, cost-delicate purchaser electronics applications. The five-part family offers densities going from 100,000 to 1.6 million framework gates. The Spartan-3E family. expands on the accomplishment of the prior spartan 3E family by expanding the measure of rationale per I/O, essentially reducing the expense per logic cell. New highlights improve framework execution and diminish the expense of arrangement. These Spartan-3E FPGA improvements, joined with cutting edge 90 nm measure innovation, convey more usefulness and transfer speed per dollar than already conceivable, setting new guidelines in the programmable logic industry. The Spartan 3E family is a better option than mask modified ASICs. This result is obtained from the synthesis report from Synopsys.
In the article, wave pipelined architecture for Polar encoder is introduced. The same is simulated using Modelsim tool and synthesized using both Synopsys and Xilinx. After the synthesis, the module is targeted to Virtex-7 VC 709 FPGA device. The test reports of the Synopsys, proved that the power dissipation area for wave pipelined architecture is more efficient compared to Conventional and other wave pipelining architectures. The absence of intermediate registers in the wave pipeline made the polar code more power efficient and efficient area overheads. It provides a method for significantly reducing clock by keeping the external functionality and timing of any circuit. The synthesis report proved that 50% of efficiency in area and Latency in the wave pipelining compared to the conventional methods.
Conflicts of interest The first author of the article, on his behalf and that of all the authors, declares that there is no potential conflict of interest related to the article.
Funding: No funding was received
Data Availability Statement All data generated or analyzed during this study are included in this published article
- Arıkan E. Channel polarization: a method for constructing capacity achieving codes for symmetric binary-input memory less channels. IEEE Transactions on Information Theory, 2009, 55(7): 3051−3073
- Arıkan E. A performance comparison of polar codes and Reed-Muller codes.IEEE communications Letters, 2008, 12(6): 447−449
- Şaşoğlu E, Telatar E, Arikan E. Polarization for arbitrary discrete memoryless channels. Proceedings of the 2009 IEEE Information Theory Workshop on Networking and Information Theory (ITW’09), Jun 10−12, 2009, Volos, Greece. Piscataway, NJ, USA: IEEE, 2009: 144−148
- Telatar E. Polar coding: a brief tour. Proceedings of the 2010 International Conference on Signal Processing and Communications (SPCOM’10), Jul 18−21, 2010, Lausanne, Switzerland. Piscataway, NJ, USA: IEEE, 2010: 2p
- Mari R, Tanaka T. Performance and construction of polar codes on symmetric binary-input memoryless channels. Proceedings of the IEEE International Symposium on Information Theory (ISIT’09), Jun 28−Jul 3, 2009, Seoul, Republic of Korea. Piscataway, NJ, USA: IEEE, 2009:−1500
- Korada S B, Şaşoğlu E, Urbanke R. Polar codes: characterization of exponent, bounds, and constructions. IEEE Transactions on Information Theory, 2010, 56(12): 6253−6264
- Korada S B. Polar codes for channel and source coding. doctoral dissertation.Ph D Thesis Lausanne, Switzerland: Ecole Polytechnique Fédérale de Lausanne (EPFL), 2009
- Goela N, Korada S B, Gastpar M. On LP decoding of polar codes. Proceedings of the 2010 IEEE Information Theory Workshop on Networking and Information Theory (ITW’10), Aug 30−Sept 3, 2010, Dublin, Ireland. Piscataway, NJ, USA: IEEE, 2010: 5p
- Bakshi M, Jaggi S, Effros M. Concatenated polar codes. Proceedings of the IEEE International Symposium on Information Theory (ISIT’10), Jun 13−18, 2010, Pasadena, CA, USA. Piscataway, NJ, USA: IEEE, 2010:918−922.
- E. Arikan, “Channel polarization: A method for constructing capacityachieving codes for symmetric binary-input memoryless channels,” IEEE Trans. Inf. Theory, vol. 55, no. 7, pp. 3051–3073, Jul. 2009.
- R. Mori and T. Tanaka, “Performance and construction of polar codes on symmetric binary-input memoryless channels,” in Proc. IEEE Int. Symp. Inf. Theory, Jun. 2009, pp. 1496–1500.
- R. Mori and T. Tanaka, “Performance of polar codes with the construction using density evolution,” IEEE Commun. Lett., vol. 13, no. 7, pp. 519–521, Jul. 2009.
- I. Tal and A. Vardy, “How to construct polar codes,” IEEE Trans. Inf. Theory, vol. 59, no. 10, pp. 6562–6582, Oct. 2013.
- P. Trifonov, “Efficient design and decoding of polar codes,” IEEE Trans. Commun., vol. 60, no. 11, pp. 3221–3227, Nov. 2012.
- J. Dai, K. Niu, Z. Si, C. Dong, and J. Lin, “Does Gaussian approximation work well for the long-length polar code construction?” IEEE Access, vol. 5, pp. 7950–7963, Apr. 2017.
- D. Wu, Y. Li, and Y. Sun, “Construction and block error rate analysis of polar codes over AWGN channel based on Gaussian approximation,” IEEE Commun. Lett., vol. 18, no. 7, pp. 1099–1102, Jul. 2014.
- G. He et al., “Beta-expansion: A theoretical framework for fast and recursive construction of polar codes,” in Proc. GLOBECOM-IEEE Global Commun. Conf., Dec. 2017, pp. 1–6.
- Y. Zhou, R. Li, H. Zhang, H. Luo, and J. Wang, “Polarization weight family methods for polar code construction,” in Proc. IEEE 87th Veh. Technol. Conf. (VTC Spring), Jun. 2018, pp. 1–5.
- A. Eslami and H. Pishro-Nik, “A practical approach to polar codes,” in Proc. IEEE Int. Symp. Inf. Theory Proc., Jul. 2011, pp. 16–20.
- K. Niu, K. Chen, and J.-R. Lin, “Beyond turbo codes: Rate-compatible punctured polar codes,” in Proc. IEEE Int. Conf. Commun. (ICC), Jun. 2013, pp. 3423–3427. [12] L. Zhang, Z. Zhang, X. Wang, Q. Yu, and Y. Chen, “On the puncturing patterns for punctured polar codes,” in Proc. IEEE Int. Symp. Inf. Theory, Jun. 2014, pp. 121–125.