- Home /

In order for network slicing to deliver on its promise as an effective tool to generate new revenues and profitability, new business models must match the dynamic technical and operational changes that it brings. Significant progress is being made in demonstrations and trials, as highlighted in this report and the...

Joe Giersch, a biologist from USGS, sat down with InterDigital to discuss technology’s role in the study of stream ecology, and explain why we should all know about the insect, Lednia tumana, that he has spent his life studying.

Recently, the Qualcomm Tricorder XPRIZE® announced its winners. We caught up with Ed Hepler, ex-InterDigital engineer and hardware development lead of the winning bootstrap operation, Final Frontier Medical Devices, after the winning announcement in this CREATORS sit-down.

Application of puncturing of a CRC code for WLANs

Monisha Ghosh, Senior Member, IEEE and Frank LaSita, Member, IEEE

{monisha.ghosh, frank.lasita}@interdigital.com

InterDigital Communications, LLC

Abstract— In some cases, like the proposed IEEE 802.11ah

draft specification [3], there arises a need to have a short

Cyclic Redundancy Check (CRC) code to detect errors on the

information bits in the various signal fields. While an optimum

CRC of the required length can be chosen for this, in order to

minimize complexity it may be desirable to “puncture” an

existing CRC generator to reduce the number of parity bits

transmitted. In this letter we evaluate puncturing of a CRC-8

generator to generate a 4-bit CRC such that the minimum

Hamming distance of the resultant code is 2.

Index Terms—CRC, puncturing, 802.11

I. INTRODUCTION

YCLIC Redundancy Codes (CRCs) are widely used in

many wired and wireless standard specifications as a

means of error detection. The simplest CRC is a 1-bit even-

parity as used for example in the IEEE 802.11a specification

[1] to protect the information bits in the signal field (SIG

bits). The CRC enables the receiver to detect whether the

SIG bits were received error-free, or not. As such, it is only

used for error detection, and not error correction. The 1-bit

parity check ensures that all single bit errors will be

detected. Since the SIG bits carry information such as the

Modulation Coding Scheme (MCS) used and number of

bytes in the following data packet, it is very important that

these bits be decoded correctly. The SIG field is usually

transmitted at the lowest supported MCS for maximum

robustness.

CRCs of various lengths have been extensively studied

and computer searches have been performed to determine

optimal generator polynomials. However, the minimum

Hamming distance of a CRC depends not only on the

generator polynomial but also on the length of the

information bits being protected by the CRC. It has been

shown in [2] that a number of commonly used CRC

generators are in fact suboptimal from a minimum

Hamming distance point of view for certain data lengths.

Recently, IEEE 802.11ah [3] has begun developing a

physical (PHY) and medium access control (MAC) layer

specification for the Sub-1 GHz non television white spaces

(non-TVWS) frequencies in the 902-928 MHz [3]. The PHY

is proposed to be a down clocked version of the IEEE

802.11ac PHY which is the standard for the 5 GHz ISM

band [4]. 802.11ac specifies an 8-bit CRC-8 for the SIG

field with generator polynomial 𝑥! + 𝑥! + 𝑥 + 1. However,

the SIG field in 802.11ah [3] is redefined to include only a

4-bit CRC. In order to keep the implementation complexity

low, it was proposed in [5] to just take the 4 least significant

bits (LSBs) of the 8-bit parity generated by the CRC-8

polynomial. We show in this paper that this choice leads to a

CRC with minimum Hamming distance of 1, i.e. there are

certain single bit error patterns that cannot be detected. We

also perform a codeword weight analysis and demonstrate

that there are other puncturing choices that can deliver a 4-

bit CRC with Hamming distance 2 and hence are more

suitable than the 4 LSBs.

The paper is organized as follows: Section II provides a

brief background of the IEEE 802.11ah specification.

Section III develops the codeword weight analysis and

Section IV presents analytical and simulation results using

the puncture patterns in Section III. Finally, Section V

concludes the paper.

II. THE IEEE 802.11AH SPECIFICATION

In order to accommodate different spectral allocations

worldwide, IEEE 802.11ah specifies two mandatory modes

of operation: a 1 MHz mode and a 2 MHz mode in the 900

MHz frequency band. One of the primary functional

requirements of the 802.11ah specification is that it shall

support a range of 1 km with at least 100 kbps throughput.

This capability will enable applications like remote

monitoring and smart metering. In order to obtain this range,

the specification proposes a new MCS called “MCS0-Rep2”

which is a mode with rate ½ convolutional coding using the

standard [133,171] convolutional code, with BPSK

modulation, followed by a repetition of the coded symbol.

This mode is specified only for the 1 MHz mode of

operation. The lowest data rate for the 2 MHz mode is the

“MCS0” mode which is simply rate ½ BPSK. Since the SIG

field is transmitted with the lowest supported data rate, the 1

MHz mode SIG field uses MCS0-Rep2, while the 2 MHz

mode SIG field uses MCS0.

A. 1 MHz SIG Field

The 1 MHz mode uses a 32-point FFT with a carrier

spacing of 31.25 kHz. Of the 32 available frequency

carriers, 24 are used for data, 2 are in-band pilots, one is the

DC which is not used and the rest are band-edge carriers.

The SIG field is defined to have 26 bits of information,

followed by a 4-bit CRC and 6 tail bits (to terminate the

convolution code) for a total of 36 bits. Using MCS0-Rep2,

the SIG field thus requires 6 OFDM symbols. In [5] it was

proposed that the 4-bit CRC be derived from the CRC-8

C

polynomial by using only the 4 LSBs.

B. 2 MHz SIG Field

The 2 MHz mode uses a 64-point FFT with a carrier

spacing of 31.25 kHz. Of the 64 available frequency

carriers, 52 are used for data, 4 are in-band pilots, one is the

DC which is not used and the rest are band-edge carriers.

Depending on the transmission mode (multi-user or single

user), there are two SIG fields specified: SIGA and SIGB.

The SIGA field is defined to have 38 bits of information,

followed by a 4-bit CRC and 6 tail bits (to terminate the

convolution code) for a total of 48 bits. Using MCS0, the

SIGA field thus requires 2 OFDM symbols. In [5] it was

proposed that the 4-bit CRC in SIGA be derived from the 8-

bit CRC generated by the CRC-8 polynomial by using only

the 4 LSBs. The SIGB field carries less information bits and

hence has room for the full 8-bit CRC derived from CRC-8.

III. CODEWORD WEIGHT ANALYSIS

Let us assume that there are 𝑁 information bits. Then, we

can form the generator matrix, G, for the polynomial 𝑥! + 𝑥! + 𝑥 + 1 as 𝐺 = 𝐼! 𝑃 where 𝐼! is an 𝑁 ×𝑁

identity matrix and 𝑃 is a 𝑁 ×8 parity matrix. The

corresponding parity check matrix, H, can then be written as 𝐻 = 𝑃! 𝐼! , where 𝐼! is an 8 ×8 identity matrix.

In order to reduce the number of parity bits from 8 to 4, 4

rows are removed from matrix 𝑃! to get a 4 ×𝑁 matrix (or 4

columns may be removed from 𝑃 ) to obtain a matrix

denoted as 𝑃!!. The new parity check matrix describing this

punctured code is then given by 𝐻! = 𝑃!! 𝐼! , where 𝐼! is

an 4 ×4 identity matrix.

In order to avoid a minimum Hamming distance of 1 for a

code created as described above, a requirement is that no

column of the parity check matrix be composed of all zeros

[6]. Therefore, when 4 rows are removed in the example

above, it is desirable for the matrix 𝐻! not to have an all-

zero column. The complete Hamming Weight (HW)

distribution of a code may be derived from the parity check

matrix as follows: the number of codewords with HW = i is

the number of combinations of i columns of the parity check

matrix such that a linear combination is equal to a zero

vector [6].

For the CRC-8 code, there are 70 combinations of 4-bit

puncturing patterns, i.e., there are 70 ways to puncture 8

parity bits to obtain 4 parity bits. Let 𝑐!𝑐!𝑐!𝑐!𝑐!𝑐!𝑐!𝑐! denote the 8 parity bits generated from the

CRC-8 polynomial where 𝑐! is the least significant bit

(LSB) and 𝑐! is the most significant bit (MSB). Table 1

shows the HW distribution for 𝑁 = 26 information bits

when a 4-bit CRC is derived by puncturing the CRC-8 code.

Only those combinations that have minimum HW = 2 are

shown, other than the MSBs and LSBs which have

minimum HW of 1. As comparison, the HW distribution of

the optimal 4-bit CRC generator using the CRC-4

polynomial 𝑥! + 𝑥 + 1

is also shown. Table 2, on the other

hand, shows a HW distribution for 𝑁 = 38 information bits

when a 4-bit CRC is derived by puncturing the CRC-8 code.

CRC bits HW =

1

HW =

2

HW =

3

HW =

4

HW =

5

c7c6c5c4

(LSBs)

3 28 254 1663 8839

c3c2c1c0

(MSBs)

2 24 247 1687 8969

c3c2c1c0

(optimal

4-bit

CRC)

0 15 280 1785 8736

c5c2c1c0 0 31 247 1658 9029

c5c3c2c0 0 34 247 1635 9029

c5c4c1c0 0 27 265 1670 8879

c5c4c2c0 0 31 252 1657 8976

c5c4c3c1 0 29 264 1658 8890 𝑁 c6c3c1c0 0 35 246 1648 8992

c6c3c2c1 0 29 260 1662 8930

c6c4c3c1 0 31 263 1646 8901

c6c5c2c0 0 33 259 1640 8909

c6c5c3c2 0 32 259 1645 8925

c7c4c2c1 0 33 248 1646 9018

c7c4c3c0 0 29 264 1658 8890

c7c4c3c1 0 29 260 1662 8930

c7c5c2c0 0 34 255 1635 8949

c7c5c4c1 0 32 266 1629 8874

c7c6c3c2 0 29 262 1674 8896

Table 1: HW distribution when a 4-bit CRC is derived from

the CRC-8 code for 26 information bits.

CRC

Bits

HW =

1

HW =

2

HW =

3

HW =

4

HW = 5

c7c6c5c4

(LSBs)

3 52 707 6932 53267

c3c2c1c0

(MSBs)

3 51 697 6947 53377

c3c2c1c0

(optimal

4-bit

CRC)

0 39 765 7101 52761

c5c3c2c0 0 65 692 6867 53564

c5c4c2c0 0 58 711 6942 53325

c6c4c3c1 0 56 720 6938 53292

c6c5c2c0 0 62 704 6894 53426

c6c5c3c2 0 58 717 6906 53339

c7c4c2c1 0 65 699 6865 53501

c7c5c4c1 0 60 721 6876 53323

Table 2: HW distribution when a 4-bit CRC is derived from

the CRC-8 code for 38 information bits.

As shown in Tables 1 and 2, if the 4 CRC bits are chosen

to be 𝑐!𝑐!𝑐!𝑐! (i.e., the four LSBs) or bits 𝑐!𝑐!𝑐!𝑐! (i.e., the

four MSBs), then the minimum Hamming distance is 1, i.e.

there are 2 to 3 single-bit error patterns that will not be

detected by the resulting code. Hence these are not good

choices for a CRC. Instead, there are other choices shown in

Tables 1 and 2 that deliver a minimum Hamming distance of

2 and hence are better choices for a CRC.

We also observe that as the number of data bits, 𝑁 ,

increases, the number of combinations that result in a code

with Hamming distance 2 decreases, e.g. from 16 to 7 when 𝑁 increases from 26 to 38. Figure 1 shows that if the

number of information bits exceeds 56, then no puncturing

combination will yield a 4-bit CRC with minimum

Hamming distance 2 that is derived from CRC-8. Instead

one would have to puncture a longer CRC. One such

possibility is the CRC-32, with polynomial 𝑥!" + 𝑥!" +𝑥!" + 𝑥!! + 𝑥!" + 𝑥!" + 𝑥!! + 𝑥!" + 𝑥! + 𝑥! + 𝑥! +𝑥! + 𝑥! + 𝑥 + 1 that is used in 802.11ah as the frame-check

sequence. Figure 1 shows that it is possible to obtain a 4-bit

CRC by puncturing the CRC-32 code for a larger number of

information bits, up to 148.

Figure 1 Generating a 4-bit CRC by puncturing CRC-8 and

CRC-32

IV. RESULTS

The probability of false positives (which is the same as

the probability of undetected error) is the probability that the

CRC indicates that the SIG bits have been received correctly

when they have not, and should be as low as possible. A

false positive detection on the CRC leads to unsuccessful

attempts at trying to decode the data packet that follows the

SIG, with erroneous information for example on MCS and

length from the incorrectly decoded SIG bits. This leads to

wasted power consumption.

It is possible to use the closed-form expression for

probability of undetected error, 𝑃!", in (1) below for the

additive white Gaussian noise (AWGN) case where it is

assumed that the information bits are uncoded, 𝑃! is the

probability of bit error in AWGN as a function of signal-to-

noise-ratio (SNR) given by 𝑃! = 0.5erfc 0.5SNR , erfc is

the complementary error function, HW(𝑖) is the Hamming

weight distribution of the code and 𝑁! is the total number of

coded bits (information + parity) [6].

𝑃!" = HW(𝑖)𝑃!! 1 − 𝑃! !!!!!!!! (1)

With 𝑁! = 42, we evaluate equation (1) above and plot

the results in Figure 2 for the optimal CRC-4 code, the

CRC-8 code with the 4 LSB puncture pattern 𝑐!𝑐!𝑐!𝑐! and

the CRC-8 code with puncture pattern 𝑐!𝑐!𝑐!𝑐!. It is clear

that the 4 LSB puncture pattern performs significantly worse

than the pattern 𝑐!𝑐!𝑐!𝑐! which is very close in performance

to the optimal CRC-4. However, it may be argued that bit

interleaved coded modulation (BICM) is used on the SIG

bits in 802.11ah and hence the result for uncoded bits in

Figure 2 does not apply there. Hence, in order to evaluate

the various puncture patterns obtained from Section III

using BICM, simulations were performed to obtain the

probability of false positives.

Figure 2 Theoretical 𝑃𝑢𝑑 performance.

From Tables 1 and 2 above, we see that the 7

combinations of parity bits in Table 2 are a subset of those

in Table 1. Since it would be desirable to have the same

puncture pattern for both 1 MHz and 2 MHz modes, these 7,

along with the 4 MSBs, 4 LSBS and the optimum CRC-4

were simulated in order to choose a common puncture

pattern.

Figure 3 shows the false positive rate for the 1 MHz mode

in AWGN. The SIG field was generated according to the

description in Section II, and ideal channel estimation and

detection were assumed. The SIG error rate does not depend

on the CRC chosen, but we see that there is almost a 1 dB

difference in the false positive rate performance between the

4 LSBs, as proposed in [5], and the best pattern which is 𝑐!𝑐!𝑐!𝑐! . This pattern also gives almost the same

performance as the optimal CRC-4 generator.

Figure 4 shows the results obtained with the 2 MHz mode

in AWGN with the same 7 patterns, with the SIG field being

generated according to the description in Section II. The

spread in performance is less than in Figure 3, but

nevertheless, the pattern 𝑐!𝑐!𝑐!𝑐! is almost as good as the

optimum CRC-4 generator.

Figure 3 False Positive Performance in the 1 MHz mode

SIG Error Rate

False Positive Rate

Figure 4 False Positive Performance in the 2 MHz mode

V. CONCLUSIONS

We have shown analytically that puncturing the 8-bit

CRC generated by the polynomial 𝑥! + 𝑥! + 𝑥 + 1 by

keeping only the 4 LSBs of the 8 parity bits leads to a code

with Hamming distance 1. This is a poor choice for any

error detecting CRC and should not be used. Instead, we

have shown, analytically and with simulations, that better

puncturing choices are available that will result in a

punctured code with Hamming distance 2. This allows the

use of a shorter CRC without requiring a different CRC

generator polynomial. We also show that for lengths beyond

56 bits it is not possible to obtain a Hamming distance 2

code by puncturing CRC-8 and instead puncturing the CRC-

32 could be considered.

REFERENCES

[1] Local and metropolitan area networks—Specific requirements; Part

11: Wireless LAN Medium Access Control (MAC) and Physical

Layer (PHY) specifications; High-speed Physical Layer in the 5 GHz

Band, Available: http://easy.intranet.gr/IEEE80211a.pdf

[2] P. Koopman and T. Chakravarty, “Cyclic Redundancy Code (CRC)

polynomial selection for embedded networks,” Available:

http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_pol

y_embedded.pdf .

[3] “Proposed specification framework for Tgah,”

https://mentor.ieee.org/802.11/dcn/11/11-11-1137-11-00ah-

specification-framework-for-tgah.docx .

[4] Local and metropolitan area networks—Specific requirements; Part

11: Wireless LAN Medium Access Control (MAC) and Physical

Layer (PHY) specifications; Amendment 4: Enhancements for Very

High Throughput for Operation in Bands below 6 GHz, IEEE

P802.11ac/D3.1, August 2012.

http://www.ieee802.org/11/private/Draft_Standards/11ac/DraftP802.1

1ac_D3.1.pdf.

[5] “SIG Field 4-bit CRC,” https://mentor.ieee.org/802.11/dcn/12/11-12-

0596-01-00ah-sig-field-4-bit-crc.pptx

[6] S. Lin and D. J. Costello, Error Control Coding (2nd Edition),

Prentice Hall, 2004.

SIG Error Rate

False Positive Rate

InterDigital develops mobile technologies that are at the core of devices, networks, and services worldwide. We solve many of the industry's most critical and complex technical challenges, inventing solutions for more efficient broadband networks and a richer multimedia experience years ahead of market deployment.

© Copyright 2017 InterDigital, Inc. All Rights Reserved