Open access peer-reviewed chapter

A Brief Overview of CRC Implementation for 5G NR

Written By

Hao Wu

Submitted: 26 September 2019 Reviewed: 17 February 2020 Published: 17 March 2020

DOI: 10.5772/intechopen.91790

Chapter metrics overview

1,245 Chapter Downloads

View Full Metrics

Abstract

In fifth generation (5G) new radio (NR), the medium access control (MAC) layer organizes the data into the transport block and transmits it to the physical layer. The transport block consists of up to million bits. When the transport block size exceeds a threshold, the transport block is divided into multiple equal size code blocks. The code block consists of up to 8448 bits. Both the transport block and the code block have a cyclic redundancy check (CRC) attached. Due to the difference in the size of the transport block and the code block, the CRC processing scheme suitable for the transport block and that suitable for the code block are different. This chapter gives an overview of the CRC implementation in 5G NR.

Keywords

  • 5G
  • NR
  • CRC
  • transport block
  • code block

1. Introduction

In order to provide high data transmission rates, the bandwidth of mobile communication systems is increasing. In fourth generation (4G) long term evolution (LTE), the maximum transmission bandwidth for one component carrier is 20 MHz [1]. In fifth generation (5G) new radio (NR), the frequency bands are divided into two parts: frequency range 1 (FR1) below 6 GHz and frequency range 2 (FR2) above 24.25 GHz. The maximum transmission bandwidth for one component carrier is 100 MHz and 400 MHz in FR1 and FR2 respectively [2]. The increasing system bandwidth brings new problems to the design of the transmitter and the receiver. In this chapter of the book, we focus on the cyclic redundancy check (CRC) implementation in 5G NR.

In 5G NR, there are many physical channels defined in the downlink and the uplink [3]. The downlink physical channels consist of the physical downlink shared channel (PDSCH), the physical downlink control channel (PDCCH), the physical broadcast channel (PBCH), etc. The uplink physical channels consist of physical uplink shared channel (PUSCH), the physical uplink control channel (PUCCH), the physical random access channel (PRACH), etc. The PDSCH and the PDSCH are mainly used to transmit data. The usage scenarios of 5G NR consist of enhanced mobile broadband (eMBB), massive machine-type communications (mMTC) and ultra-reliable and low latency communications (URLLC) [4, 5]. The usage scenario of the eMBB requires high data transmission rates. As a consequence, we focus on the PDSCH and the PUSCH in this chapter.

The medium access control (MAC) layer organizes the data into the transport block and transmits it to the physical layer. In 5G NR, the maximum transport block size is 1,277,992 [6]. The processing of the transport block is shown in Figure 1 [7]. If the transport block size is larger than 3824, a 16-bit CRC is added at the end of the transport block. Otherwise, a 24-bit CRC is added at the end of the transport block. The transport block is divided into multiple equal size code blocks when the transport block size exceeds a threshold. For quasi-cyclic low-density parity-check code (QC-LDPC) base graph 1, the threshold is equal to 8448. For QC-LDPC base graph 2, the threshold is equal to 3840. In 5G NR, the maximum code block size number is 8448. An additional 24-bit CRC is added at the end of each code block when there is a segmentation. Due to the difference in the size of the transport block and the code block, the CRC processing scheme suitable for the transport block and that suitable for the code block are different.

Figure 1.

The transport block and the code block.

The rest of this chapter is organized as follows. Section 2 describes the system model of the transport block and the code block in 5G NR. Section 3 gives two properties of the CRC. Section 4 presents the overview of the CRC implementation. Finally, Section 5 gives the conclusion.

Advertisement

2. System model

Let a=a0a1aL1aLaL+1aL+N1 be the transport block including the transport block level CRC, where L is the transport block size and N is the transport block level CRC size. Note that p=aLaL+1aL+N1 is the transport block level CRC. If L is smaller than or equal to 3824, then N is equal to 16 and p is generated by the following cyclic generator polynomial:

g16x=x16+x12+x5+1E1

If L is larger than 3824, then N is equal to 24 and p is generated by the following cyclic generator polynomial:

g24Ax=x24+x23+x18+x17+x14+x11+x10+x7+x6+x5+x4+x3+x+1E2

When L+N is larger than M, the transport block including the transport block level CRC is segmented into multiple code blocks. Let R be code rate of the initial transmission indicated by the modulation and coding scheme (MCS) index. If L>292 and R>0.67 or L>3824 and R>0.25, then QC-LDPC base graph 1 is used and M is equal to 8448. Otherwise, QC-LDPC base graph 2 is used and M is equal to 3840.

When there is no segmentation, the number of code blocks C is equal to 1. When there is a segmentation, the number of code blocks C is equal to

C=L+N/M24E3

In the following sections, we mainly consider the case that there is a segmentation. Let ci=c0ic1icK1i be the ith code block, where K is the code block size and is equal to

K=L+N/C+24E4

Note that the procedure of the transport block size determination guarantees that L+N is divisible by C. cK24icK23icK1i is the code block level CRC, which is generated by the cyclic generator polynomial

g24Bx=x24+x23+x6+x5+x+1E5

cji is equal to

cji=aiK24+jE6

where 0jK25. In the following, the processing of the transport block includes: QC-LPDC encoding, rate matching, bit interleaving and code block concatenation. The encoded transport block is transmitted over the air after the symbol level processing.

At the receiver side, the following steps are carried out for the transport block: code block segmentation, bit de-interleaving, de-rate matching, QC-LPDC decoding, code block concatenation. We need to check whether each code block and the transport block are correctly received. Let di=d0id1idK1i be the ith received code block after the hard decision and e=e0e1eL+N1 be the received transport block after the hard decision. ej is equal to

ej=duvE7

wherev=j/K24, u=modjK24 and 0jL+N1. The undetected error probability is required to be less than 10−6 in 5G NR [8, 9]. Since the parity check capacity of QC-LDPC codes alone cannot meet the undetected error probability requirement of 5G NR [8, 9], we need to use the CRC check to determine whether di and e are correctly received.

Advertisement

3. Properties of the CRC

In this section, we give two properties of the CRC. These properties are useful in the CRC implementation. Before giving these properties, we define some variables. Let Ax and Bx be the polynomials. Let gx be the cyclic generator polynomial. CRCgxAx is defined as the remainder when Ax is divided by gx. The two properties are listed as follows.

Property 1.

CRCgxAxBx=CRCgxCRCgxAxCRCgxBxE8

Property 1 implies that CRCgxAxBx can be obtained by computing the CRC of Ax and Bx independently.

Property 2.

CRCgxAx+Bx=CRCgxAx+CRCgxBx.E9

Property 2 implies that CRCgxAx+Bx can be obtained by computing the CRC of Ax and Bx independently.

The proof of the property 1 and the property 2 can be found in Refs. [10, 11]. It is omitted for brevity. gx in the expression of CRCgxAx is clear from the context. As a consequence, gx in the expression of CRCgxAx is omitted in the following.

Advertisement

4. Overview of the CRC implementation

In this section, we give an overview of the CRC implementation. In the following, the received transport block after the hard decision e is used as an example. The implementation is easily generalized to other cases.

4.1 CRC implementation by direct calculation

In this scheme, the CRC of e is directly calculated by the division of polynomial using modulo-2 arithmetic.

Figure 2 illustrates an example. The dividend is equal to x5+x4+x+1 and the divisor is equal to x2+x+1. The division of polynomial begins by putting x5+x4+x3 below x5+x4. Subtracting and bringing down the next term give us the intermediate variable x3+x. This process is repeated until the degree of the intermediate variable is less than 2. Finally, we obtain that the quotient is equal to x3+x+1 and the remainder is equal to x. That is,

Figure 2.

The division of polynomial using modulo-2 arithmetic.

CRCx5+x4+x+1=xE10

The division of polynomial using modulo-2 arithmetic is a computationally intensive operation. In the worst case, it requires a shift operation and an XOR logic operation for each bit of e. As a consequence, this scheme is rarely used in actual systems. In order to solve the problem of the direct calculation, many schemes have been proposed in the literatures.

For example, the CRC implementation for gx=x5+x3+x+1 is shown in Figure 3 [12, 13]. The parallelism of this CRC implementation is 1 and thus one bit is processed on every clock cycle. Multiple bits can be processed on every clock cycle to speed the CRC calculation. For example, another CRC implementation for gx=x5+x3+x+1 is shown in Figure 4 [14, 15]. The parallelism of this CRC implementation is 3 and thus three bits are processed on every clock cycle. From Figures 3 and 4, it is clear that parallelism comes at the expense of the increased circuit complexity.

Figure 3.

CRC implementation for gx=x5+x3+x+1.

Figure 4.

CRC implementation for gx=x5+x3+x+1.

4.2 CRC implementation by parallel processing

In this scheme,e is segmented into multiple blocks and the CRC of each block is obtained by parallel processing. e is segmented into multiple blocks [16]:

e0,e1,,eM1E11

The size of eM1 is n and the size of ej is m, where 0jM2. Note that L+N is equal to n+mM1. As a consequence, e can be expressed as

e=e0xM2m+n+e1xM3m+n++eM3xn+m+eM2xn+eM1

The CRC of e is given by

CRCe=CRCe0xM2m+n++eM2xn+eM1=CRCCRCe0CRCxM2m+n++CRCeM2CRCxn+CRCeM1=CRCCRCe0CRCxM2m++CRCeM2CRCxn+CRCeM1E12

The above expression explains how CRCe is obtained. The detail is shown in Figure 5. CRCxm,CRCx2m,,CRCxM2m and CRCxn do not depend on the transport block size and can be precomputed. Since n is in the range 0m1, variables that need to be precomputed include

Figure 5.

CRC implementation by parallel processing.

CRCx1,CRCx2,,CRCxm1,CRCxm,CRCx2m,,CRCxM2mE13

As a consequence, the number of variables that needs to be precomputed is m+M3.

It is clear that the memory that needs to store the variables increases with the transport block size. To reduce the memory, CRCxαm can be recursively calculated by using CRCxm [17]. That is, CRCxαm is recursively obtained by the following expression

CRCxαm=CRCCRCxα1mCRCxmE14

In this way, the variables that need to be precomputed include

CRCx1,CRCx2,,CRCxm1,CRCxmE15

As a consequence, the number of variables that needs to be precomputed is m.

4.3 CRC implementation by serial processing

In this scheme, e is segmented into multiple blocks and the CRC of each block is obtained by serial processing. e is segmented into multiple blocks [18]:

e0,e1,,eM1E16

The size of eM1 is n and the size of ej is m, where 0jM2. Note that L+N is equal to n+mM1. e can be expressed as

e=e0xM2m+n+e1xM3m+n++eM3xn+m+eM2xn+eM1E17

The CRC of e is given by

T1=CRCe0xp1m++e1p1T2=CRCepxp1m++e2p1+CRCT1xmpTe=CRCee1pxp1m++eep1+CRCTe1xmpTe+1=CRCeepxMep2m++eM2+CRCTexMeP1mTe+2=CRCTe+1xn+CRCeM1E18

where e=M1/P. The above expression explains how CRCe is calculated. The detail is shown in Figure 6. CRCxm,CRCx2m,,CRCxp1m and CRCxn do not depend on the transport block size and can be precomputed. Since n is in the range 0m1, variables that need to be precomputed include

Figure 6.

CRC implementation by serial processing.

CRCx1,CRCx2,,CRCxm1,CRCxm,CRCx2m,,CRCxp1mE19

As a consequence, the number of variables that needs to be precomputed is m+p2.

It is clear that the memory that needs to store the variables increases with the transport block size. To reduce the memory, CRCxαmcan be recursively calculated by using CRCxm [17]. That is, CRCxαm is recursively obtained by the following expression

CRCxαm=CRCCRCxα1mCRCxmE20

In this way, the variables that need to be precomputed include

CRCx1,CRCx2,,CRCxm1,CRCxmE21

As a consequence, the number of variables that needs to be precomputed is m.

4.4 The Sarwate algorithm

Sarwate proposes an algorithm based on the lookup table [19]. The detail and the proof of the algorithm can be found in [19]. The Sarwate algorithm is shown in Figure 7 [20]. The Sarwate algorithm uses a single table of 256 32-bit elements and reads the bits byte by byte. Modern processors usually access 32 bits or 64 bits at a time. As a consequence, the Sarwate algorithm is not efficient. Some schemes have been proposed in the literatures to solve this problem.

Figure 7.

The Sarwate algorithm.

4.5 The slicing-by-4 and slicing-by-8 algorithms

Kounavis and Berry propose the slicing-by-4 and slicing-by-8 algorithms based on the lookup table [20]. The detail and the proof of the algorithms can be found in [20]. The slicing-by-4 and slicing-by-8 algorithms are shown in Figures 8 and 9 respectively [20]. The slicing-by-4 algorithm uses four tables of 256 32-bit elements and reads 32 bits at a time. The slicing-by-8 algorithm uses eight tables of 256 32-bit elements and reads 64 bits at a time. The performance of the slicing-by-4 and slicing-by-8 algorithms is improved compared to the Sarwate algorithm.

Figure 8.

The slicing-by-4 algorithm.

Figure 9.

The slicing-by-8 algorithm.

Advertisement

5. Conclusion

In 5G NR, the transport block consists of up to million bits and the code block consists of up to 8448 bits. Due to the difference in the size of the transport block and the code block, the scheme of the CRC processing suitable for the transport block and that suitable for the code block are different. This chapter gives an overview of the CRC implementation in 5G NR.

Advertisement

Conflict of interest

The authors declare no conflict of interest.

References

  1. 1. Erik D, Stefan P, Johan S. 4G: LTE/LTE-advanced for Mobile Broadband. 2nd ed. Oxford, UK: Elsevier; 2014
  2. 2. Erik D, Stefan P, Johan S. 5G NR: The Next Generation Wireless Access Technology. London, UK: Elsevier; 2018
  3. 3. 3GPP TS 38.211, V15.3.0, NR; Physical channels and modulation (Release 15). 2018-09
  4. 4. Hyoungju J, Sunho P, Jeongho Y, Younsun K, Juho L, Byonghyo S. Ultra-reliable and low-latency communications in 5G downlink: Physical layer aspects. IEEE Wireless Communications. 2018;25:124-130. DOI: 10.1109/MWC.2018.1700294
  5. 5. Petar P, Kasper Floe T, Osvaldo S, Giuseppe D. 5G wireless network slicing for eMBB, URLLC, and mMTC: A communication-theoretic view. IEEE Access. 2018;6:55765-55779. DOI: 10.1109/ACCESS.2018.2872781
  6. 6. 3GPP TS 38.214, V15.3.0, NR; physical layer procedures for data (Release 15). 2018-09
  7. 7. 3GPP TS 38.212, V15.3.0, NR; multiplexing and channel coding (Release 15). 2018-09
  8. 8. R1-1713458. Qualcomm Incorporated, CRC attachment. 3GPP TSG RAN Meeting #90; August 21–25, 2017; Prague, Czechia
  9. 9. Hao W. Hard decision of the zero a posteriori LLR in 5G NR. Internet Technology Letters. 2020;3:e146. DOI: 10.1002/itl2.146
  10. 10. Yan S, Min SK. A table-based algorithm for pipelined CRC calculation. In: Proceedings of the IEEE International Conference on Communications (ICC’10); 23-27 May 2010; Cape Town, South Africa: IEEE; 2010. pp. 1-5
  11. 11. Hao W, Fang W, Yuqing Y. A distributed CRC early termination scheme for high throughput QC-LDPC codes. In: Proceedings of International Conference on Wireless Communications and Signal Processing (WCSP) (WCSP ’18); 18-20 October 2018; Hangzhou, China: IEEE; 2018. pp. 1-5
  12. 12. TongBi P, Charles Z. High-speed parallel CRC circuits in VLSI. IEEE Transactions on Communications. 1992;40:653-657. DOI: 10.1109/26.141415
  13. 13. Richard EB. Algebraic Codes for Data Transmission. Cambridge, UK: Cambridge University Press; 2003
  14. 14. Chao C, Keshab KP. High-speed parallel CRC implementation based on unfolding, pipelining, and retiming. IEEE Transactions on Circuits and Systems II: Express Briefs. 2006;53:1017-1021. DOI: 10.1109/TCSII.2006.882213
  15. 15. Keshab KP. VLSI Digital Signal Processing Systems: Design and Implementation. New York, USA: John Wiley & Sons; 1999
  16. 16. Ji HM, Killian E. Fast parallel CRC algorithm and implementation on a configurable processor. In: Proceedings of the IEEE International Conference on Communications (ICC’02); 28 April-2 May 2002. New York, USA: IEEE; 2002. pp. 1813-1817
  17. 17. Hyeji K, Injun C, Wooseok B, Jong-yeol L, Ji-Hoon K. Distributed CRC architecture for high-radix parallel turbo decoding in LTE-advanced systems. IEEE Transactions on Circuits and Systems II: Express Briefs. 2015;62:906-910. DOI: 10.1109/TCSII.2015.2435131
  18. 18. Hao W, Tao L, Jin X, Fang W. Parallel CRC architecture for broadband communication systems. Electronics Letters. 2017;53:1439-1441. DOI: 10.1049/el.2017.1029
  19. 19. Sarwate DV. Computation of cyclic redundancy checks via table look-up. Communications of the ACM. 1988;31:1008-1014. DOI: 10.1145/63030.63037
  20. 20. Michael EK, Frank LB. Novel table lookup-based algorithms for high-performance CRC generation. IEEE Transactions on Computers. 2008;57:1550-1560. DOI: 10.1109/TC.2008.85

Written By

Hao Wu

Submitted: 26 September 2019 Reviewed: 17 February 2020 Published: 17 March 2020