Module puncture 

Puncturing of the convolutional and turbo codes: rate-compatible patterns, the punctured block codes and the free distance of a punctured code.

Model

A rate-$1/n$ code emits $n$ bits per trellis step; a Puncturer of period $P$ keeps the bit $i$ of step $t$ when the entry $(i, t \bmod P)$ of its pattern, an $n \times P$ matrix of 0 and 1, is 1. With $w$ ones in the pattern, the rate becomes $P / w$ (Cain, Clark & Geist 1979). The receiver puts back a zero LLR at every punctured position: in the Viterbi and BCJR branch metric $\sum_{i} (1 - 2c_{i}) L_{i} / 2$ of crate::conv a zero contributes nothing, which is the standard treatment of a dummy (“stolen”) bit (IEEE 802.11-2020, Sec. 17.3.5.6).

The patterns of the standards are provided as constructors:

Constructor	Source	Pattern (row $i$ = output $i$)
Puncturer::ieee80211_2_3	IEEE 802.11-2020, Sec. 17.3.5.6, Figure 17-9	A: 1 1, B: 1 0
Puncturer::ieee80211_3_4	IEEE 802.11-2020, Sec. 17.3.5.6, Figure 17-9	A: 1 1 0, B: 1 0 1
Puncturer::ieee80211_5_6	IEEE 802.11-2020, Sec. 19.3.11.6, Figure 19-11	A: 1 1 0 1 0, B: 1 0 1 0 1
Puncturer::dvbs_2_3	ETSI EN 300 421 V1.1.2, Table 2	Y: 1 1, X: 1 0
Puncturer::dvbs_3_4	ETSI EN 300 421 V1.1.2, Table 2	Y: 1 1 0, X: 1 0 1
Puncturer::dvbs_5_6	ETSI EN 300 421 V1.1.2, Table 2	Y: 1 1 0 1 0, X: 1 0 1 0 1
Puncturer::dvbs_7_8	ETSI EN 300 421 V1.1.2, Table 2	Y: 1 1 1 1 0 1 0, X: 1 0 0 0 1 0 1
Puncturer::turbo_1_2	Berrou, Glavieux & Thitimajshima 1993, Sec. II	systematic: 1 1, parity 1: 1 0, parity 2: 0 1

all for the $(133, 171){8}$ code of constraint length 7 in the output order of ConvolutionalCode::k7 ($133{8}$ first), but the last, for the three streams of a turbo code. IEEE 802.11 emits A from $133_{8}$ and B from $171_{8}$, so its rows are in the printed order; DVB-S emits X from $G_{1} = 171_{8}$ and Y from $G_{2} = 133_{8}$ (EN 300 421, Sec. 4.4.3), so the rows of its Table 2 are given Y first. The two standards then puncture the same codes: the patterns of rates 2/3, 3/4 and 5/6 are defined once, by IEEE 802.11, and the DVB-S constructors of these rates are aliases kept under the name of their standard. They keep the bits of DVB-S but send $Y$ before $X$ at every step; the transmitted order of the standard, $X$ first, is that of comnum_systems::dvb::InnerRate.

A rate matching that transmits some bits of a word, once or several times, is a BitSelection: output bit $t$ carries bit $\pi(t)$ of the word, and the receiver sums the LLRs of every bit over its copies (zero for a bit never sent). A puncturer is one (Puncturer::selection), as are the circular buffers of 5G NR (crate::nr).

Punctured wraps a BlockCode whose coded bits are in step-major order (the ConvolutionalCode, tail included), and PuncturedTurbo a TurboCode whose codeword is the systematic, first-parity and second-parity streams (the pattern is applied across the three streams at every information index; the tail bits are kept). The rate matching of 3GPP (TS 36.212, Sec. 5.1.4: sub-block interleaving and a circular buffer) is not a periodic pattern and is not provided.

free_distance computes the free distance of a punctured code from its trellis, a shortest path on the $2^{K-1} \times P$ states of the periodically time-varying trellis; it reproduces the tables of Yasuda, Kashiki & Hirata (1984).

Examples

use comnum_fec::block::BlockCode;
use comnum_fec::conv::ConvolutionalCode;
use comnum_fec::puncture::{Punctured, Puncturer, free_distance};
let code = Punctured::new(ConvolutionalCode::k7(100)?, Puncturer::ieee80211_3_4())?;
assert_eq!(code.n(), 35 * 4 + 2);                 // 4 bits kept of every 6, 2 of the last 2
let info: Vec<u8> = (0..100).map(|i| ((i * 5) % 7 < 3) as u8).collect();
let c = code.encode_block(&info)?;
let llr: Vec<f64> = c.iter().map(|&b| if b == 0 { 4.0 } else { -4.0 }).collect(); // noiseless
assert_eq!(code.decode_block(&llr)?, info);
assert_eq!(free_distance(code.code().trellis(), code.puncturer())?, 5);

References

1. J. B. Cain, G. C. Clark and J. M. Geist, “Punctured convolutional codes of rate $(n-1)/n$ and simplified maximum likelihood decoding,” IEEE Trans. Inf. Theory, 25(1), 97–100, 1979.
2. Y. Yasuda, K. Kashiki and Y. Hirata, “High-rate punctured convolutional codes for soft decision Viterbi decoding,” IEEE Trans. Commun., 32(3), 315–319, 1984, Table I.
3. IEEE Std 802.11-2020, Sec. 17.3.5.6 (Figure 17-9) and Sec. 19.3.11.6 (Figure 19-11).
4. ETSI EN 300 421 V1.1.2, Digital Video Broadcasting (DVB); Framing structure, channel coding and modulation for 11/12 GHz satellite services, 1997, Sec. 4.4.3, Table 2.
5. C. Berrou, A. Glavieux and P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding: turbo-codes,” Proc. IEEE ICC, 1064–1070, 1993, Sec. II.

Structs

BitSelection

The bits of a word of full_len bits that a rate matching transmits: output bit $t$ carries bit positions()[t] of the word (a bit may be sent several times, or never).

Punctured

A block code whose coded bits (in step-major order) are punctured: the ConvolutionalCode.

PuncturedTurbo

A turbo code whose systematic and parity streams are punctured by a pattern of three rows (systematic, parity 1, parity 2) applied at every information index; the tail bits are kept.

Puncturer

A periodic puncturing pattern over the $n$ outputs of a code (see the module).

Functions

free_distance

The free distance of the code of trellis punctured by puncturer: the smallest weight of a transmitted path that leaves the zero state and returns to it, over every phase of the pattern. A shortest path over the $2^{K-1} P$ (state, phase) nodes of the time-varying trellis (Bellman–Ford, the weights being the numbers of kept ones of the branches).