comnum_fec/block.rs
1//! The interface shared by the block codes.
2//!
3//! A [`BlockCode`] maps $k$ information bits to $n$ coded bits and decodes $n$ LLRs
4//! (positive for a 0, the convention of `comnum_core::signal`) back to $k$ bits. Its
5//! provided methods encode and decode streams of whole blocks, and every code of the
6//! crate implements the verb traits [`Encode`](comnum_core::traits::Encode) and
7//! [`Decode`](comnum_core::traits::Decode) on the multi-stream containers. A code whose
8//! decoder gives the a posteriori LLRs of its information bits also implements
9//! [`SoftDecode`].
10
11use comnum_core::{Error, Result};
12
13/// A code of $k$ information bits and $n$ coded bits per block.
14pub trait BlockCode {
15 /// Information bits per block.
16 fn k(&self) -> usize;
17
18 /// Coded bits per block.
19 fn n(&self) -> usize;
20
21 /// Encode one block of $k$ bits.
22 ///
23 /// # Errors
24 /// [`Error::Shape`] if `info` does not have $k$ bits.
25 fn encode_block(&self, info: &[u8]) -> Result<Vec<u8>>;
26
27 /// Decode one block of $n$ LLRs into $k$ bits.
28 ///
29 /// # Errors
30 /// [`Error::Shape`] if `llr` does not have $n$ values.
31 fn decode_block(&self, llr: &[f64]) -> Result<Vec<u8>>;
32
33 /// Encode one block of $k$ bits into the $n$ values of `out` (ADR 0011: the default
34 /// copies [`BlockCode::encode_block`]; a code overrides it when a profile shows the
35 /// copy).
36 ///
37 /// # Errors
38 /// [`Error::Shape`] if `info` does not have $k$ bits or `out` $n$ values.
39 fn encode_block_into(&self, info: &[u8], out: &mut [u8]) -> Result<()> {
40 let c = self.encode_block(info)?;
41 comnum_core::same_len(out.len(), c.len(), "coded bits")?;
42 out.copy_from_slice(&c);
43 Ok(())
44 }
45
46 /// Decode one block of $n$ LLRs into the $k$ values of `out` (as
47 /// [`BlockCode::encode_block_into`]).
48 ///
49 /// # Errors
50 /// [`Error::Shape`] if `llr` does not have $n$ values or `out` $k$ values.
51 fn decode_block_into(&self, llr: &[f64], out: &mut [u8]) -> Result<()> {
52 let d = self.decode_block(llr)?;
53 comnum_core::same_len(out.len(), d.len(), "decoded bits")?;
54 out.copy_from_slice(&d);
55 Ok(())
56 }
57
58 /// Code rate $k/n$.
59 fn code_rate(&self) -> f64 {
60 self.k() as f64 / self.n() as f64
61 }
62
63 /// Encode whole blocks.
64 ///
65 /// # Errors
66 /// [`Error::Shape`] if the number of bits is not a multiple of $k$.
67 fn encode_stream(&self, info: &[u8]) -> Result<Vec<u8>> {
68 let k = self.k();
69 whole_blocks(info.len(), k, "bits")?;
70 let mut out = Vec::with_capacity(info.len() / k * self.n());
71 for b in info.chunks(k) {
72 out.extend(self.encode_block(b)?);
73 }
74 Ok(out)
75 }
76
77 /// Decode whole blocks.
78 ///
79 /// # Errors
80 /// [`Error::Shape`] if the number of LLRs is not a multiple of $n$.
81 fn decode_stream(&self, llr: &[f64]) -> Result<Vec<u8>> {
82 let n = self.n();
83 whole_blocks(llr.len(), n, "LLRs")?;
84 let mut out = Vec::with_capacity(llr.len() / n * self.k());
85 for b in llr.chunks(n) {
86 out.extend(self.decode_block(b)?);
87 }
88 Ok(out)
89 }
90}
91
92/// A block code whose decoder gives the a posteriori LLRs of the information bits: the
93/// soft output of an iterative receiver (turbo equalisation, iterative demapping) or of
94/// a concatenation.
95///
96/// Implemented by the [`LdpcCode`](crate::ldpc::LdpcCode) (belief propagation), the
97/// [`ConvolutionalCode`](crate::conv::ConvolutionalCode) (BCJR, log-MAP), the
98/// [`TurboCode`](crate::turbo::TurboCode), the [`NrLdpc`](crate::nr::NrLdpc) code, and
99/// the punctured codes [`Punctured`](crate::puncture::Punctured) and
100/// [`PuncturedTurbo`](crate::puncture::PuncturedTurbo), which put back a zero LLR at the
101/// punctured positions. The list decoder of the polar codes gives hard candidates only
102/// ([`PolarCode::decode_list`](crate::polar::PolarCode::decode_list)).
103///
104/// # Model
105///
106/// With the channel LLRs $L_{c}$ of the $n$ coded bits and the a priori LLRs $L_{a}$ of
107/// the $k$ information bits $u_{i}$ (zero if `None`),
108///
109/// $$
110/// L_{\mathrm{app}}(u_{i}) = \ln \frac{P(u_{i} = 0 \mid L_{c}, L_{a})}{P(u_{i} = 1 \mid L_{c}, L_{a})},
111/// $$
112///
113/// exact for the BCJR algorithm, approximated by the iterative decoders; the extrinsic
114/// information of the code is $L_{\mathrm{app}} - L_{a}$ minus the channel LLR of a
115/// systematic bit. The hard decisions of $L_{\mathrm{app}}$ are those of
116/// [`BlockCode::decode_block`] for the iterative codes; a convolutional code decodes its
117/// blocks by Viterbi (maximum-likelihood sequence) and its soft output by BCJR
118/// (maximum a posteriori bit), which may differ on a few bits.
119pub trait SoftDecode: BlockCode {
120 /// The a posteriori LLRs of the $k$ information bits into `out`, from the $n$
121 /// channel LLRs `llr` and the $k$ a priori LLRs `apriori`; returns the iterations
122 /// of the decoder (1 for a non-iterative one, 0 when the input was already a
123 /// codeword for the LDPC codes).
124 ///
125 /// # Errors
126 /// [`Error::Shape`] if `llr` does not have $n$ values, or `apriori` or `out` $k$.
127 fn app_into(&self, llr: &[f64], apriori: Option<&[f64]>, out: &mut [f64]) -> Result<usize>;
128
129 /// [`SoftDecode::app_into`] into a new vector.
130 ///
131 /// # Errors
132 /// As [`SoftDecode::app_into`].
133 ///
134 /// # Examples
135 /// ```
136 /// use comnum_fec::block::{BlockCode, SoftDecode};
137 /// use comnum_fec::turbo::TurboCode;
138 /// let code = TurboCode::lte(40)?;
139 /// let info: Vec<u8> = (0..40).map(|i| (i % 3 == 1) as u8).collect();
140 /// let llr: Vec<f64> = code.encode_block(&info)?.iter().map(|&b| if b == 0 { 2.0 } else { -2.0 }).collect();
141 /// let app = code.app(&llr, None)?;
142 /// assert_eq!(comnum_core::signal::hard_decisions(&app), info);
143 /// # Ok::<(), comnum_core::Error>(())
144 /// ```
145 fn app(&self, llr: &[f64], apriori: Option<&[f64]>) -> Result<Vec<f64>> {
146 let mut out = vec![0.0; self.k()];
147 self.app_into(llr, apriori, &mut out)?;
148 Ok(out)
149 }
150}
151
152pub(crate) use comnum_core::expect_len;
153
154/// `Encode` and `Decode` on the multi-stream containers for a [`BlockCode`], every
155/// stream encoded (decoded) as whole blocks: `container_traits!(Code)`, or with generic
156/// parameters `container_traits!(Punctured<C>, C: BlockCode)`.
157macro_rules! container_traits {
158 ($t:ty) => {
159 $crate::block::container_traits!($t,);
160 };
161 ($t:ty, $($g:tt)*) => {
162 impl<$($g)*> comnum_core::traits::Encode for $t {
163 fn rate(&self) -> f64 {
164 $crate::block::BlockCode::code_rate(self)
165 }
166
167 fn encode_into(
168 &self,
169 info: &comnum_core::signal::Bits,
170 out: &mut comnum_core::signal::Bits,
171 ) -> comnum_core::Result<()> {
172 let (k, n) = ($crate::block::BlockCode::k(self), $crate::block::BlockCode::n(self));
173 $crate::block::whole_blocks(info.len(), k, "bits")?;
174 out.resize(info.n_streams(), info.len() / k * n);
175 for s in 0..info.n_streams() {
176 let o = out.stream_mut(s);
177 for (b, c) in info.stream(s).chunks(k).zip(o.chunks_mut(n)) {
178 $crate::block::BlockCode::encode_block_into(self, b, c)?;
179 }
180 }
181 Ok(())
182 }
183 }
184
185 impl<$($g)*> comnum_core::traits::Decode for $t {
186 fn decode_into(
187 &mut self,
188 llr: &comnum_core::signal::Llr,
189 out: &mut comnum_core::signal::Bits,
190 ) -> comnum_core::Result<()> {
191 let (k, n) = ($crate::block::BlockCode::k(self), $crate::block::BlockCode::n(self));
192 $crate::block::whole_blocks(llr.len(), n, "LLRs")?;
193 out.resize(llr.n_streams(), llr.len() / n * k);
194 for s in 0..llr.n_streams() {
195 let o = out.stream_mut(s);
196 for (l, d) in llr.stream(s).chunks(n).zip(o.chunks_mut(k)) {
197 $crate::block::BlockCode::decode_block_into(self, l, d)?;
198 }
199 }
200 Ok(())
201 }
202 }
203 };
204}
205pub(crate) use container_traits;
206
207/// [`Error::Shape`] unless `len` values make whole blocks of `block` (for the container
208/// traits and the streams).
209pub(crate) fn whole_blocks(len: usize, block: usize, what: &str) -> Result<()> {
210 if block == 0 || len % block != 0 {
211 return Err(Error::Shape(format!("{len} {what} is not a multiple of the block length {block}")));
212 }
213 Ok(())
214}
215
216pub(crate) use comnum_math::{Jacobian, max_star};
217
218/// Helpers of the tests of the codes.
219#[cfg(test)]
220pub(crate) mod testing {
221 use comnum_core::rng::Rng;
222
223 /// The LLRs of the bits `c` sent in BPSK ($1 - 2b$) over a real AWGN channel of
224 /// variance `s2`: one Gaussian draw per bit, the LLRs $2 y / \sigma^{2}$ (the link of
225 /// `comnum_validation::bpsk_awgn_llr`; the code crate holds no modulation).
226 pub(crate) fn awgn_llr(c: &[u8], s2: f64, rng: &mut Rng) -> Vec<f64> {
227 let s = s2.sqrt();
228 c.iter().map(|&b| 2.0 * ((1.0 - 2.0 * f64::from(b)) + s * rng.gaussian()) / s2).collect()
229 }
230}