2.1 Encoder shift register

The 802.11 BCC is a rate-\(\frac{1}{2}\), constraint-length-\(7\) convolutional encoder (⊕Forney Jr. 1970Forney Jr., G. D. 1970. “Convolutional Codes I: Algebraic Structure.” IEEE Transactions on Information Theory 16 (6): 720–38.) with generator polynomials \[g_1 = 133_8 = (1,0,1,1,0,1,1), \qquad g_2 = 171_8 = (1,1,1,1,0,0,1).\] In polynomial form, with \(D\) the unit-delay operator, \[g_1(D)=1+D^2+D^3+D^5+D^6, \qquad g_2(D)=1+D+D^2+D^3+D^6.\] These generators were identified by Odenwalder (⊕Odenwalder 1970Odenwalder, J. P. 1970. “Optimal Decoding of Convolutional Codes.” PhD thesis, University of California, Los Angeles.) as maximising free distance at rate \(\frac{1}{2}\), \(K=7\), standardised by CCSDS (⊕Consultative Committee for Space Data Systems 2013Consultative Committee for Space Data Systems. 2013. “Telemetry Channel Coding.” CCSDS 131.0-B-3. Washington, DC, USA: CCSDS.), and adopted in IEEE 802.11 (“IEEE Std 802.11-2020: IEEE Standard for Information Technology — Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications” 2021). At each clock cycle the encoder reads one input bit \(u_n\), shifts it into a 6-stage register, and XORs selected taps to produce two output bits \((v_n^{(1)}, v_n^{(2)})\).

IEEE 802.11 K=7 BCC shift-register encoder. Each D box is a unit-delay; ⊕ is mod-2 addition. The g₁=133₈ XOR chain runs above (taps 0,2,3,5,6); g₂=171₈ runs below (taps 0,1,2,3,6).

2.2 Trellis state

The encoder state \(\sigma_n=(u_{n-1},\ldots,u_{n-6})\in\{0,\ldots,63\}\). A transition \(\sigma\xrightarrow{u}\sigma'\) is (⊕Forney Jr. 1970Forney Jr., G. D. 1970. “Convolutional Codes I: Algebraic Structure.” IEEE Transactions on Information Theory 16 (6): 720–38.; ⊕Lin and Costello Jr. 2004Lin, S., and D. J. Costello Jr. 2004. Error Control Coding. 2nd ed. Upper Saddle River, NJ, USA: Pearson Prentice Hall.): \[\sigma'=\bigl((\sigma\ll 1)\;\&\;\texttt{0x3F}\bigr)\;|\;u, \qquad v^{(k)}=\bigoplus_{i=0}^{6}g_k[i]\cdot r_i,\quad \mathbf{r}=(u,\sigma_0,\ldots,\sigma_5).\] The trellis (⊕Forney Jr. 1973Forney Jr., G. D. 1970. “Convolutional Codes I: Algebraic Structure.” IEEE Transactions on Information Theory 16 (6): 720–38. 1973. “The Viterbi Algorithm.” Proceedings of the IEEE 61 (3): 268–78.) has 64 states, each with two outgoing branches.

Rate-1/2 trellis, 4 lowest states over n=0,…,7. Blue solid: u=0; red dashed: u=1. Edge labels (v⁽¹⁾v⁽²⁾) shown at first transition only.

3.1 Rate \(\frac{1}{2}\) — unpunctured

\[\mathbf{P}_{1/2}=\begin{pmatrix}1\\1\end{pmatrix},\quad\mathbf{p}=(1,1).\]

3.2 Rate \(\frac{2}{3}\)

\[\mathbf{P}_{2/3}=\begin{pmatrix}1&1\\1&0\end{pmatrix},\quad\mathbf{p}=(1,1,1,0),\quad L=4.\]

3.3 Rate \(\frac{3}{4}\)

\[\mathbf{P}_{3/4}=\begin{pmatrix}1&1&0\\1&0&1\end{pmatrix},\quad\mathbf{p}=(1,1,1,0,0,1),\quad L=6.\]

3.4 Rate \(\frac{5}{6}\)

\[\mathbf{P}_{5/6}=\begin{pmatrix}1&1&0&1&0\\1&0&1&0&1\end{pmatrix},\quad\mathbf{p}=(1,1,1,0,0,1,1,0,1,0),\quad L=10.\]

IEEE 802.11 puncture masks and free distances.

Rate-3/4 mask 111001 over two periods. Solid border: transmitted. Dashed: deleted.

5.1 Union bound on bit-error probability

For the Viterbi decoder (⊕Viterbi 1967Viterbi, A. J. 1967. “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm.” IEEE Transactions on Information Theory 13 (2): 260–69.; ⊕Forney Jr. 1973Forney Jr., G. D. 1970. “Convolutional Codes I: Algebraic Structure.” IEEE Transactions on Information Theory 16 (6): 720–38. 1973. “The Viterbi Algorithm.” Proceedings of the IEEE 61 (3): 268–78.) over AWGN with BPSK, the pairwise error probability at Hamming distance \(d\) is (⊕Proakis 2001Proakis, J. G. 2001. Digital Communications. 4th ed. New York, NY, USA: McGraw-Hill.; ⊕Ryan and Lin 2009Ryan, W. E., and S. Lin. 2009. Channel Codes: Classical and Modern. Cambridge, UK: Cambridge University Press.) \[P_2(d)=Q\!\left(\sqrt{2d\,R_c\,\frac{E_b}{N_0}}\right).\] The union-bound bit-error probability is (⊕Viterbi 1967Viterbi, A. J. 1967. “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm.” IEEE Transactions on Information Theory 13 (2): 260–69.; ⊕Lin and Costello Jr. 2004Lin, S., and D. J. Costello Jr. 2004. Error Control Coding. 2nd ed. Upper Saddle River, NJ, USA: Pearson Prentice Hall.) \[P_b\;\lesssim\;\sum_{d=d_\mathrm{free}}^{D_{\max}}\beta_d\;Q\!\left(\sqrt{2d\,R_c\,\frac{E_b}{N_0}}\right). \tag{UB}\]

5.2 Frame error rate

\[P_f\;\lesssim\;\sum_{d=d_\mathrm{free}}^{D_{\max}}\alpha_d\;Q\!\left(\sqrt{2d\,R_c\,\frac{E_b}{N_0}}\right). \tag{FER}\]

5.3 Single-term approximation

\[P_b\;\approx\;\beta_{d_\mathrm{free}}\;Q\!\left(\sqrt{2\,d_\mathrm{free}\,R_c\,\frac{E_b}{N_0}}\right).\]

Union-bound BEP and FER (10 spectrum terms, BPSK/AWGN).

The union bound is loose at low SNR but tightens rapidly in the waterfall region (⊕Forney Jr. 1973Forney Jr., G. D. 1970. “Convolutional Codes I: Algebraic Structure.” IEEE Transactions on Information Theory 16 (6): 720–38. 1973. “The Viterbi Algorithm.” Proceedings of the IEEE 61 (3): 268–78.). The rate-1/2 code provides roughly 4–5 dB coding gain at \(P_b=10^{-5}\) (⊕Heller and Jacobs 1971Heller, J. A., and I. M. Jacobs. 1971. “Viterbi Decoding for Satellite and Space Communication.” IEEE Transactions on Communication Technology 19: 835–48.; ⊕Proakis 2001Proakis, J. G. 2001. Digital Communications. 4th ed. New York, NY, USA: McGraw-Hill.). Figure \(\ref{fig:ber_fer}\) shows both bounds.

BEP (left) and FER (right, K=1024) union bounds with simulation markers for all four IEEE 802.11 BCC rates over AWGN/QPSK. Lines: bounds (30 terms); dot-dashed+markers: Monte Carlo. Dotted black: uncoded BPSK.

6.1 Channel model and penalty factor \(\Delta_M\)

Under the BICM model (⊕Caire, Taricco, and Biglieri 1998Caire, Giuseppe, Giorgio Taricco, and Ezio Biglieri. 1998. “Bit-Interleaved Coded Modulation.” IEEE Transactions on Information Theory 44 (3): 927–46. https://doi.org/10.1109/18.669123.), the pairwise error probability at distance \(d\) becomes \[P_2(d)\leq Q\!\left(\sqrt{2\,R_c\,d\,\Delta_M\,\frac{E_b}{N_0}}\right),\qquad \Delta_M=\frac{3\,m}{2(M-1)},\quad m=\log_2 M,\quad M\geq 4.\] For QPSK (\(M=4\)), \(\Delta_M=1\), recovering the BPSK result.

Modulation penalty factor. Each QAM order step costs roughly 4–5 dB.

6.2 Union bounds

Substituting \(\Delta_M\) into the BPSK bounds replaces \(E_b/N_0\) by \(\Delta_M E_b/N_0\). Setting \(\Delta_M=1\) recovers (UB) and (FER) exactly.

BEP union bounds for Gray-coded M-QAM (30 spectrum terms). Left: rate 1/2, varying M; dotted: uncoded references. Right: 256-QAM, all four rates; dot-dashed+markers: Monte Carlo for R=2/3 and R=3/4.

7.1 Why augment the state

For the unpunctured code the transfer function method uses a \(64\times64\) state space (⊕Lin and Costello Jr. 2004Lin, S., and D. J. Costello Jr. 2004. Error Control Coding. 2nd ed. Upper Saddle River, NJ, USA: Pearson Prentice Hall.; ⊕Viterbi and Omura 1979Viterbi, A. J., and J. K. Omura. 1979. Principles of Digital Communication and Coding. New York, NY, USA: McGraw-Hill.). Puncturing makes branch weight phase-dependent; augmenting the state with the puncture phase \(\phi\in\{0,\ldots,L-1\}\) converts this to a time-invariant problem (⊕Hagenauer 1988Hagenauer, J. 1988. “Rate-Compatible Punctured Convolutional Codes (RCPC Codes) and Their Applications.” IEEE Transactions on Communications 36 (4): 389–400.). The augmented state is \((\sigma,\phi)\); for rate-3/4 (\(L=6\)) this gives \(64\times6=384\) states.

Each branch carries weight \(D^d N^u\) where \(d=p_\phi v^{(1)}+p_{(\phi+1)\bmod L}v^{(2)}\). Branches partition into \(\mathbf{E}\): START\(\to\mathcal{S}\); \(\mathbf{Q}\): \(\mathcal{S}\to\mathcal{S}\); \(\mathbf{R}\): \(\mathcal{S}\to\)START.

E/Q/R partition of the augmented trellis. The transfer function sums over all first-return paths from START to START.