{'fraction_non_alphanumeric': 0.03599456354947608, 'fraction_numerical': 0.009250734359244159, 'mean_word_length': 4.6600496277915635, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
CRC Codes as Error Correction Codes

CRC codes have long since been adopted in a vast range of applications. The established notion that they are suitable primarily for error detection can be set aside through use of the recently proposed Guessing Random Additive Noise Decoding (GRAND). Hard-detection (GRAND-SOS) and soft-detection (ORBGRAND) variants can decode any short, high-rate block code, making them suitable for error correction of CRC-coded data. When decoded with GRAND, short CRC codes have error correction capability that is at least as good as popular codes such as BCH codes, but with no restriction on either code length or rate. The state-of-the-art CA-Polar codes are concatenated CRC and Polar codes. For error correction, we find that the CRC is a better short code than either Polar or CA-Polar codes. Moreover, the standard CA-SCL decoder only uses the CRC for error detection and therefore suffers severe performance degradation in short, high rate settings when compared with the performance GRAND provides, which uses all of the CA-Polar bits for error correction. Using GRAND, existing systems can be upgraded from error detection to low-latency error correction without re-engineering the encoder, and additional applications of CRCs can be found in IoT, Ultra-Reliable Low Latency Communication (URLLC), and beyond. The universality of GRAND, its ready parallelized implementation in hardware, and the good performance of CRC as codes make their combination a viable solution for low-latency applications.


I. INTRODUCTION
Owing to the simplicity of their implementation and their powerful error detection capability, Cyclic Redundancy Checks (CRCs) [1] are widely adopted in applications in storage, networking, and communications. CRCs are sometimes used not only to error detect, but also to assist in error correction. For example, to assist in early stopping of Turbo decoding iterations [2], or joint decoding of CRCs and convolutional codes [3]. In list decoding architectures, a CRC is commonly used for selection from a list of candidates. This technique has been applied to Turbo codes [4] and Polar codes (CA-Polar) [5]- [7]. The latter leads to the success of CRCaided successive cancellation list (CA-SCL or SCL for brief) decoding algorithms. The better performance at shorter code lengths of CA-Polar codes, as compared to other common Shannon limit approaching codes, such as Turbo codes and LDPC codes [8], has led to their inclusion in 5G-NR control communications where latency is of particular concern [9].
With the error correction capability enabled by CRC, significant benefits can be brought to existing systems, but have heretofore seen only limited use. For example, the Automatic Repeat Request (ARQ) scheme of networking can be upgraded to Hybrid ARQ through the use of CRC's error correction. Similar benefits can be found in IoT or personal area network (PAN). Previous research on the use of CRCs for error correction focused only on fixing one or two erroneous bits [10], [11]. Soft detection techniques such as Belief Propagation (BP) and Linear Programming (LP) [12] have also been considered for decoding CRCs, but their performance is severely limited when used for short and high rate codes. No previous approach leads to a broadly applicable decoding method capable of extracting the maximum error correction performance from CRCs.
Many emerging applications require low latency communication of small packets of data. Examples include machine communications in IoT systems [13]- [15], telemetry, tracking, and command in satellite communications [16], [17], all control channels in mobile communication systems, and Ultra-Reliable Low Latency Communications (URLLC) as proposed in 5G-NR [18]- [20]. Most codes and decoders were designed to function well for large blocks of data, but provide underwhelming performance for short codes. As a result, some conventional codes have received renewed attention [21]- [23], including Reed-Solomon Codes [24], BCH codes [25] and Random Linear Codes (RLC). In this paper, we show that CRCs stand out as a viable class of error correcting codes.
The error correction capability of CRCs is enabled by the recently introduced Guessing Random Additive Noise Decoding (GRAND) algorithm [26], [27], which can decode any short, high-rate block codes. GRAND's universality stems from its effort to identify the effect of the noise, from which the code-word is deduced. Originally introduced as a hard detection decoder [26]- [28], a series of soft detection variants, SRGRAND [29], [30], ORBGRAND [31] and SGRAND [32], have since been proposed that make distinct quantization assumptions. Both hard and soft detection versions of GRAND are ML decoders. The simplicity of GRAND's operation has resulted in the proposal of efficient circuit implementations [33].
With GRAND and standard decoders if available, we evaluate CRCs as short, high-rate error correction codes when compared with BCH, RLCs and CA-Polar codes. Using the best published CRC generator polynomials [34] we find that CRCs perform as well as BCH codes at their available settings, but CRCs can operate for a wider range of code lengths and rates. Featuring even more flexible code-book settings, RLCs possess security potentials by code-book re-randomisation, but at very high code-rates RLC performance degrades in comparison to select CRCs. Using GRAND to compare the performance of Polar, CA-Polar and CRC codes, we find that that the CRC is not aiding so much as dominating the decoding performance potential. Furthermore, the celebrated CA-SCL algorithm underperforms for short packets because the CRC bits are only used for error detection.
The rest of the paper is organized as follows. Section II introduces GRAND hard and soft detection variants. Section III review CRC and other comparison candidates. Section IV provides simulated performance evaluation of involved channel codes. Section V summarizes the paper's findings.

II. GUESSING RANDOM ADDITIVE NOISE DECODING A. GRAND-SOS for hard detection
Consider a transmitted binary code-word X n ∈ C drawn from an arbitrary rate R code-book C, i.e. a set of 2 nR = 2 K strings in {0, 1} n , where (n, K) is a core pair of parameters of a codebook. Assume independent post-hard-detection channel noise, N n , which also takes values from {0, 1} n , additively alters X n between transmission and reception. The resulting sequence is Y n = X n ⊕ N n , where ⊕ represents addition modulo 2.
From Y n GRAND attempts to determine X n indirectly by identifying N n through sequentially taking putative noise sequences, z n , which we sometimes term patterns, subtracting them from the received signal and querying if what remains, Y n ⊕ z n , is in the code-book C. If transmitted code-words are all equally likely and z n are queried in order from most likely to least likely based on the true channel statistics, the first instance where a code-book element is found is an optimally accurate maximum likelihood decoding in the hard detection setting [27]. For the hard detection binary symmetric channels (BSC) channels considered in this paper the order of testing noise patterns z n,i , i = 1, 2, ..., n follows their Hamming weight from low to high. For patterns with identical Hamming weights, we choose a sweeping order of generation, in which a grouped pattern sweeps from one end of sequence to the other end. A new grouped pattern is obtained by permuting the bits in the group. When permutation exhausts, an extra nonflipped bit is included and the permutation process restarts. This pattern generator gives the decoder some advantages with burst errors (specifically treated in [28]) and the resulted algorithm is named as GRAND with simple order sweeping (GRAND-SOS).
It is established in [27] that one need not query all possible noise patterns for the decoder to be capacity-achieving, and instead one can determine a threshold for the number of codebook queries, termed the abandonment threshold, at which a failure to decode can be reported without unduly impacting error correction performance. Standard decoders of linear block codes can decode up to t = d/2 errors where d is the minimum distance of the code-book [35]. Using this limit as abandonment threshold, GRAND is guaranteed to achieve at least equivalent performance to existing code-book dedicated decoders.

B. ORBGRAND for soft detection
Ordered reliability bits GRAND (ORBGRAND) is a soft detection approximate ML decoder that features significant complexity advantage over the full ML soft GRAND (SGRAND) decoder [32], and still provides better BLER performance than state-of-the-art soft decoders [31] for short, high-rate codes.
Soft detection versions of GRAND require reliability information of each received code-word bit. With binary phase-shift key (BPSK) modulation and additive white Gaussian noise (AWGN) channels, the reliability is simply the absolute value of the received signal, from which the probability of a test pattern can be computed and used for its testing order. Facing the fact that efficient implementation of this simple idea is not computational straight-forward, ORBGRAND develops an efficient method to generate a approximate optimal order that is universal.
Assume the reliability order index of the k − th received bit is r n k ∈ (1, 2, ..., n). The vector r n records the reliability orders of all received bits in Y n . A reliability weighted Hamming weight called Logistic Weight for z n is defined as, This metric is used to determine the checking order of testing noise sequences z n,i , i = 1, 2, ..., n, i.e. w L (z n,i ) < w L (z n,j ) for i < j. Patterns with identical Logistic Weights can be arbitrarily ordered. The performance of soft decoders is no longer restricted by minimum distance of code-books. In most cases ORBGRAND with a moderate complexity can provide better performance than state-of-the-art soft decoders.

III. OVERVIEW OF CHANNEL CODES A. CRC codes
As a type of cyclic code [36], CRC operates in terms of polynomial computation based on Galois field of two elements GF (2). The CRC generator polynomial can be expressed as g k x k , where n − K is the number of CRC bits to be appended to a message sequence, expressed as polynomial m(x) = K−1 i=0 m i x i , with n being the code-word length. The CRC code-word is constructed as, with the remainder of polynomial division appended to the shifted message polynomial, the resulting code-word polynomial c(x) is divisible by g(x). The property is used in parity checks to detect errors, and provides an efficient implementation for checking code-book membership in GRAND. While Equation (2) presents the systematic format of CRC codes, they can also be constructed as other cyclic codes (such as BCH) as, Equation (3) generates the same code-book as (2), but with lower computation complexity.
To maximize the number of detectable errors, the CRC maximizes the minimum Hamming distance of its code-book. The topic has been studied extensively and optimal generator polynomials have been published for a wide set of combinations of CRC bit numbers and message lengths [34], [37], [38]. Unlike channel codes for error correction function, the design of CRC codes need not consider decoder implementation, indicating potentially better decoding performance than normal Forward Error Correction (FEC) codes, provided that a decoder is available, i.e. GRAND.

B. Other short code candidates
Also as a type of cyclic codes, BCH codes can be constructed with Equation (3). In this sense, BCH codes can be viewed as a special case of CRC codes. For any positive integers m > 3 and t < 2 m−1 , there exists a binary BCH code with code-word length of n = 2 m − 1, parity bit number of n − K ≤ mt and minimum distance of d ≥ 2t + 1. A list of available parameters n, K and t can be found in [35]. The standard decoder for BCH codes is Berlekamp-Massey (B-M) decoder [25], which is also used for the widely adopted Reed-Solomon (RS) codes, a special type of BCH codes with operations extended to higher order Galois fields. It should be noted that the original proposal of GRAND has no limitation on the Galois field order [27], Here we focus on binary codes, but the methodology can be easily extended to RS codes in higher order Galois fields.
RLCs are linear block codes that have long been used for theoretical investigation, but have heretofore not been considered practical in terms of decodability. With GRAND, RLCs are no more challenging to decode than any other linear codes. Their generator matrices are obtained by appending a randomly generated parity component to the identity matrix, from which the parity check matrix can be computed accordingly. In addition to its flexibility, the ease of codebook construction grants RLC security features by real-time code-book updates.
CA-Polar codes are concatenated CRC and Polar codes. Although they approach the Shannon reliable rate limit [5], Polar codes do not give satisfactory decoding performance for practical code-word lengths, even with the ML successive cancellation (SC) algorithm. A CRC is introduced as an outer code to assist decoding and the CA-SCL decoding algorithm was invented as the key to the success of the resulted CA-Polar codes [6], [7]. In the decoding process, a list of candidate codewords are produced and CRC checks are performed to make the selection with confidence. There is to our knowledge no standard hard detection decoder for Polar or CA-Polar codes apart from GRAND decoders. For code-book membership checking in GRAND, parity check matrices can be easily derived for generator matrices, which, for linear block codes, can be obtained with a simple method that injects each vector of the K-by-K identity matrix to the encoder and collects the output vectors.

IV. SIMULATED PERFORMANCE EVALUATION
For our simulations, we map the stationary bit flip probability of the channel energy per transmitted information bit via the usual AWGN BPSK formula: p = Q 2RE b /N 0 , where R is the code rate. Table I lists the code-book settings considered for CRC evaluation, along with published preferred generator polynomials. Note that the zero order 1 is omitted in the least significant bit [34].

A. CRC Codes vs BCH Codes
For code-book settings in Table I available for BCH codes, we measure the performance of the following code/decoder combinations: • BCH codes with Berlekamp-Massey (B-M) decoders • BCH codes with GRAND-SOS decoder and AB > t • CRC codes with GRAND-SOS decoder and AB > t • CRC codes with GRAND-SOS decoder and AB > 4 AB > t indicates abandonment when the error number in testing patterns is larger than the code-book decoding capability, t. And AB > 4 is a loose condition for all available BCH codes listed in Table I, with which we show the influence of the minimum distance of a code-book to its decoding performance. Simulation results for code-word length of 127 are presented in Fig. 1.
For each code rate, all four code/decoder combinations have performance curves that are close to each other, leading to the following conclusions. For BCH codes, the GRAND-SOS algorithm has the same decoding capability as the standard Berlekamp-Massey decoder. With identical code-book settings, CRC codes have matching performances to BCH codes. Loosening abandonment condition grants little improvement to decoding performance of GRAND, so the use of abandonment to curtail complexity remains attractive. These observations are further confirmed with simulations of code-word length of 63, as shown in Fig. 2 Combined evaluation of curves in Fig. 1 and Fig. 2 indicates that performance of short codes is sensitive to code-word lengths and rates, therefore the flexibility of CRC renders it attractive vis-à-vis BCH codes in low-latency scenarios.

B. CRC Codes vs RLCs
To explore fully the decoding capability of RLC codes, we update the generator matrix for every code-word transmission to achieve random selection of code-words. For a fair comparison, we apply the same abandonment threshold for CRC and RLC codes. In Fig. 3, the RLC(128, 99) curve overlaps the CRC(128, 99) curve. As the code rate increases, however, the RLC performance degrades in comparison to the CRC code, owing to the shrinking of code-word space that makes it more probable for RLC to pick up code-words close to each other. The generator polynomial of CRC, however, is the product of a selection procedure [37], [38] that thus results in a code-book with stable minimum distance. This suggests that to extract near-CRC code performance for very high rate RLCs, extra structure might be needed.

C. Comparison with Polar and CA-Polar Codes
In 5G mobile systems, an 11-bit CRC (CRC11) is specified for uplink CA-Polar codes, and a 24-bit CRC (CRC24) for downlink. We evaluate performance of Polar codes with or without aid from CRC11 and CRC24, and compare them to CRC codes from in Table I, for code-book with (n, K) set to (128, 99). Hard detection ML performance when decoded with GRAND-SOS are presented in Fig. 4. A generous abandonment threshold AB > 5 is chosen to avoid influence from computation complexity on code performance.
Let us first assess code performance under a hard detection scenario. The Polar(128, 99) code without the CRC shows significantly worse performance than the three other codes. This is reasonable considering that Polar codes are closely related to Reed-Muller codes [39], which are known to be inferior to cyclic codes (such as BCH). The introduction of CRC codes, either CRC11 or CRC24, sufficiently breaks the undesirable structure in Polar code, bringing its performance close to that achieved by CRC29. In this sense, the "aid" from CRC is so effective that it may be preferable just to use the CRC as an error-correcting code, considering that significant encoding complexity can be saved thanks to the simple implementation of CRC encoders.
Having considered performance under hard detection, let us envisage soft detection performance, which is of particular importance given that prevailing decoders for Polar codes are soft decoders, especially when a non-trivial decoding gain is expected [35]. The extra gain comes from decoding errors beyond the hard detection decoding capability t. Therefore we use the number of code-book checks as the abandonment condition in this case, with AB > 5e6 being a generous threshold that ensures optimal decoding performance. A gain of about 1.5 dB from soft decoding at BLER= 10 −3 can be observed by comparing Fig. 4 and Fig. 5. Of more interest is that under the same ORBGRAND decoding power four candidate codes follow identical performance ranking as their hard detection behaviors, i.e. CRC assists Polar codes to approach the best performance achieved by the CRC code itself. Evaluating the performance of the SC and CA-SCL soft decoding algorithms in Fig. 5, a surprising phenomenon can be observed. While SC decoding of the Polar code and CA-SCL of the CRC11 aided Polar code provide comparable performance to ORBGRAND, the performance of CA-SCL with the CRC24 aided Polar code dramatically degrades to a level even worse than the hard detection performance of the same code in Fig. 4. This reveals a previously unnoticed issue with the CA-SCL algorithm. As a list decoding algorithm, CA-SCL produces a set of candidate code-words in its decoding procedure and use CRC checks to make candidate selection. More CRC bits provide better error detection capability and consequently higher confidence in candidate checks. However, the redundancy introduced by CRC bits to the code-book is ignored for error correction, leaving the remaining Polar bits to produce the redundancy required for the error correcting list decoding. With a given code-book (n, K) set of parameters, if the number of CRC bits is excessive relative to the limited number of Polar redundant bits, then the decoder may experience limited space of list candidates and, consequently, performance loss, in spite of the enhanced selection confidence from the extra CRC bits. As the key contributor to the error correcting quality of CA-Polar codes, the CA-SCL algorithm has been applied mostly to long codes, in which this shortcoming, which has been unnoticed so far to our knowledge, is far from negligible on these short codes. In Fig. 5, the CA-Polar (128, 99) with CRC11 does not experience this performance loss, owing to the 18 Polar bits, which are still sufficient to provide enough list candidate space. Unfortunately this success is not guaranteed with shorter code-word lengths or with higher coding rates. Fig.  6 displays the same short-coming of the CA-SCL algorithm with the CRC11 but in CA-Polar(64,51), while ORBGRAND is stably successful.
The superior performance of CRC codes when compared to Polar codes, CRC aided or not, with their ultra low encoding complexity, and the robust decoding performance of ORBGRAND as compared to CA-SCL algorithm, all suggest that a CRC code with ORBGRAND as its decoder provides a better short code solution than Polar or CA-Polar codes.

V. SUMMARY
Despite being the most widely used error detection solution in storage and communication, CRC codes have not been considered seriously as error correcting codes owing to the absence of an appropriate decoder. Instead, their main contribution has been in assisting state-of-the-art list decoders, with CA-Polar codes as the most successful recent example. With the invention of GRAND, the possibility of considering CRCs as error correction codes can be realized.
Here we consider hard and soft detection variants, GRAND-SOS and ORBGRAND, to evaluate the performance of CRC codes in comparison with other candidate short, high-rate codes, including BCH codes, RLCs and CA-Polar codes. As short codes, CRCs not only provide at least equivalent decoding performance to existing solutions, but are superior in various aspects. Compared to to BCH codes, CRC codes have no restriction on code lengths and rates. For very high rate codes, RLCs are outperformed by CRC codes. Polar codes are surpassed by CRC codes in both hard and soft detection BLER performance. Aided by CRC, CA-Polar code can provide a matching performance, but the CRC alone still wins with its ultra low encoding complexity. In addition, CA-SCL decoder, as the key to practical adoption of CA-Polar code, suffers significant performance loss when CRC bits dominate the code's redundancy. The reason is that CA-SCL uses CRC checks for candidate selection in list decoding, but does not avail of the CRC bits for error correction. ORBGRAND, on the other hand, is robust in all scenarios. Therefore, CRC with GRAND as its decoder is a good solution to low latency applications requiring short codes.