comnum_spec/blocks/coding/
codes.rs

1//! The codes of `fec_encode` and `fec_decode`: their parameters, the LDPC construction
2//! built once, and [`build_code`].
3
4use crate::blocks::schema::{ParamType, variants_schema};
5use crate::blocks::{ParamInfo, Params};
6use comnum_core::{Error, Result};
7use comnum_fec::block::BlockCode;
8use comnum_fec::conv::ConvolutionalCode;
9use comnum_fec::crc::Crc;
10use comnum_fec::ldpc::{self, CheckRule, LdpcCode};
11use comnum_fec::polar::PolarCode;
12use comnum_fec::puncture::{Punctured, Puncturer};
13use comnum_fec::rs::ReedSolomon;
14use comnum_fec::turbo::{TurboCode, TurboDecoder};
15use comnum_math::Jacobian;
16use serde::Deserialize;
17use serde_json::Value as Json;
18
19// ------------------------------------------------------------------------- codes
20
21block_params! {
22    struct ConvSpec {
23        k: usize [required] "bits" >= 1, "information bits per codeword";
24        hard: bool [false], "hard-decision Viterbi decoding";
25        puncture: Option<String> [absent "unpunctured"],
26            "puncturing pattern of comnum_fec::puncture::Puncturer::from_name (ieee80211_2_3, dvbs_3_4…)";
27    }
28}
29
30block_params! {
31    struct RsSpec {
32        m: u32 [required] "bits" >= 2 <= 16, "bits per symbol: the field GF(2^m)";
33        t: usize [required] "symbols", "symbol errors corrected";
34        n: Option<usize> [absent "2^m - 1"] "symbols", "length of the shortened code";
35        first_root: usize [1], "first root b of the generator α^b, …";
36        root_step: usize [1], "step c between the roots of the generator";
37        poly: Option<u32> [absent "the conventional primitive polynomial of degree m"],
38            "field polynomial, bit i the coefficient of x^i (CCSDS: 391 = 0x187, x^8 + x^7 + x^2 + x + 1)";
39    }
40}
41
42block_params! {
43    struct TurboSpec {
44        k: usize [required] "bits" >= 8, "information bits: an interleaver length of LTE";
45        iterations: usize [8], "decoding iterations";
46        max_log: bool [false], "max-log-MAP instead of log-MAP";
47    }
48}
49
50block_params! {
51    /// The construction and the decoder of a PEG LDPC code: the parameters shared by
52    /// the `ldpc` code of `fec_encode` and `fec_decode` and by `pas_encode` and
53    /// `pas_decode`.
54    pub(super) struct LdpcSettings {
55        var_degree: usize [ldpc::DEFAULT_VAR_DEGREE => "3"] >= 1, "variable-node degree of the PEG code";
56        seed: u64 [ldpc::DEFAULT_PEG_SEED => "1"], "seed of the PEG construction";
57        rule: String [ldpc::DEFAULT_RULE.name() => "sum_product"]
58            one_of ["sum_product", "min_sum", "normalized_min_sum", "offset_min_sum"],
59            "check-node rule";
60        alpha: f64 [ldpc::DEFAULT_ALPHA => "0.8"], "scale or offset of min-sum";
61        layered: bool [ldpc::DEFAULT_LAYERED => "true"], "layered schedule";
62        iterations: usize [ldpc::DEFAULT_MAX_ITERATIONS => "50"] >= 1, "decoding iterations at most";
63    }
64}
65
66/// The regular LDPC code of length `n` with `k` information bits and variable-node
67/// degree `var_degree` built by progressive edge growth from `seed`, built once:
68/// `fec_encode` and `fec_decode` (and `pas_encode` and `pas_decode`) build the same
69/// code from one mapping, and the construction is deterministic.
70fn peg(n: usize, k: usize, var_degree: usize, seed: u64) -> Result<LdpcCode> {
71    /// The codes built, by `(n, k, var_degree, seed)`, the last ones kept.
72    type Built = Vec<((usize, usize, usize, u64), LdpcCode)>;
73    static BUILT: std::sync::Mutex<Built> = std::sync::Mutex::new(Vec::new());
74    const KEPT: usize = 8;
75    let key = (n, k, var_degree, seed);
76    let found = BUILT.lock().ok().and_then(|b| b.iter().find(|(k, _)| *k == key).map(|(_, c)| c.clone()));
77    if let Some(c) = found {
78        return Ok(c);
79    }
80    let c = LdpcCode::peg(n, k, var_degree, seed)?;
81    if let Ok(mut b) = BUILT.lock() {
82        if b.len() == KEPT {
83            b.remove(0);
84        }
85        b.push((key, c.clone()));
86    }
87    Ok(c)
88}
89
90impl LdpcSettings {
91    /// The regular LDPC code of length `n` with `k` information bits built by
92    /// progressive edge growth, with these decoder settings.
93    pub(super) fn code(&self, n: usize, k: usize) -> Result<LdpcCode> {
94        let mut c = peg(n, k, self.var_degree, self.seed)?;
95        c.decoder.rule = CheckRule::from_name(&self.rule, self.alpha)?;
96        c.decoder.layered = self.layered;
97        c.decoder.max_iterations = self.iterations;
98        Ok(c)
99    }
100}
101
102block_params! {
103    struct LdpcSpec {
104        n: usize [required] "bits", "length of the codeword";
105        k: usize [required] "bits", "information bits";
106        settings: LdpcSettings [flatten], "the construction and the decoder";
107    }
108}
109
110block_params! {
111    struct PolarSpec {
112        n: usize [required] "bits", "length of the codeword, a power of 2";
113        k: usize [required] "bits", "information bits (a CRC comes on top)";
114        design_ebn0_db: f64 [2.0] "dB", "Eb/N0 of the Gaussian-approximation design";
115        crc: Option<String> [absent "no CRC"], "CRC of CRC-aided SCL: crc6, crc11, crc16, crc24a, crc24b, crc24c";
116        list: usize [1], "list size (1: successive cancellation)";
117    }
118}
119
120/// The documentation of the parameters of a code.
121type ParamsFn = fn() -> Vec<ParamInfo>;
122
123/// The codes of `fec_encode` and `fec_decode`: the value of their `type` and their
124/// parameters.
125const CODES: [(&str, ParamsFn); 5] = [
126    ("conv", ConvSpec::params),
127    ("rs", RsSpec::params),
128    ("turbo", TurboSpec::params),
129    ("ldpc", LdpcSpec::params),
130    ("polar", PolarSpec::params),
131];
132
133/// The value of the `code` parameter: a mapping with the `type` of the code and its
134/// parameters, described in the documentation and the JSON Schema of the blocks.
135#[derive(Clone, Deserialize)]
136#[serde(transparent)]
137pub(super) struct Code(pub(super) Json);
138
139impl ParamType for Code {
140    fn schema() -> Json {
141        variants_schema(&Code::variants())
142    }
143
144    fn variants() -> Vec<(&'static str, Vec<ParamInfo>)> {
145        CODES.iter().map(|&(kind, params)| (kind, params())).collect()
146    }
147}
148
149/// Build a code from its specification (a mapping with a `type`).
150///
151/// # Errors
152/// [`comnum_core::Error::Config`] for an unknown type or invalid parameters.
153pub fn build_code(v: &Json) -> Result<Box<dyn BlockCode + Send + Sync>> {
154    let mut p = match v {
155        Json::Object(o) => o.clone(),
156        other => return Err(Error::Config(format!("a code is a mapping with a type, got {other}"))),
157    };
158    let names = CODES.map(|(k, _)| k);
159    let Some(Json::String(given)) = p.remove("type") else {
160        return Err(Error::Config(format!("a code needs a type among {names:?}")));
161    };
162    let kind =
163        crate::blocks::schema::choice(&names, &given).ok_or_else(|| crate::unknown("code type", &given, &names))?;
164    let what = format!("{kind} code");
165    let p = Json::Object(p);
166    Ok(match kind {
167        "conv" => {
168            let ConvSpec { k, hard, puncture } = ConvSpec::parse(&what, p)?;
169            let mut code = ConvolutionalCode::k7(k)?;
170            code.hard_decision = hard;
171            match puncture {
172                None => Box::new(code),
173                Some(name) => {
174                    Box::new(Punctured::new(code, Puncturer::from_name(&name).map_err(|e| e.context("conv"))?)?)
175                }
176            }
177        }
178        "rs" => {
179            let RsSpec { m, t, n, first_root, root_step, poly } = RsSpec::parse(&what, p)?;
180            let n = n.unwrap_or((1usize << m) - 1);
181            let poly = poly.or_else(|| comnum_math::gf2m::primitive_polynomial(m)).unwrap_or(0);
182            Box::new(ReedSolomon::with_field(m, poly, first_root, root_step, t, n)?)
183        }
184        "turbo" => {
185            let TurboSpec { k, iterations, max_log } = TurboSpec::parse(&what, p)?;
186            let mut code = TurboCode::lte(k)?;
187            code.decoder = TurboDecoder { iterations, jacobian: Jacobian::from_max_log(max_log) };
188            Box::new(code)
189        }
190        "ldpc" => {
191            let q = LdpcSpec::parse(&what, p)?;
192            Box::new(q.settings.code(q.n, q.k)?)
193        }
194        "polar" => {
195            let PolarSpec { n, k, design_ebn0_db, crc, list } = PolarSpec::parse(&what, p)?;
196            let mut c = PolarCode::new(n, k, design_ebn0_db)?;
197            if let Some(name) = crc {
198                c = c.with_crc(Crc::from_name(&name)?)?;
199            }
200            Box::new(c.with_list(list)?)
201        }
202        _ => unreachable!("a name of CODES"),
203    })
204}
205
206#[cfg(test)]
207mod tests {
208    // the fields of the parameters are private to this module
209    use super::super::pas::PasSpec;
210    use super::*;
211    use serde_json::json;
212
213    #[test]
214    fn the_ccsds_recipe_of_the_rs_block_builds_the_code_of_ccsds() {
215        // CCSDS 131.0-B-5, Secs. 4.3.3 and 4.3.4: the field of 0x187 (391), the roots
216        // alpha^(11 j), j = 112 ... 143; the conventional field 0x11D gives another code
217        let spec = json!({"type": "rs", "m": 8, "t": 16, "first_root": 112, "root_step": 11, "poly": 391});
218        let code = build_code(&spec).unwrap();
219        let ccsds = comnum_fec::ccsds::CcsdsRs::new(16, 1, 0).unwrap();
220        let info: Vec<u8> = (0..code.k()).map(|i| u8::from(i % 7 == 3)).collect();
221        assert_eq!(code.encode_block(&info).unwrap(), ccsds.code().encode(&info).unwrap());
222        let other = json!({"type": "rs", "m": 8, "t": 16, "first_root": 112, "root_step": 11});
223        assert_ne!(build_code(&other).unwrap().encode_block(&info).unwrap(), ccsds.code().encode(&info).unwrap());
224    }
225
226    #[test]
227    fn the_ldpc_defaults_are_those_of_com_fec() {
228        use crate::blocks::schema::ParamDefault;
229        // the PAS blocks and the LDPC code of fec_encode document the same defaults
230        for params in [PasSpec::params(), LdpcSpec::params()] {
231            let shown: Vec<(&str, String, Json)> = params
232                .into_iter()
233                .filter_map(|p| match p.default {
234                    ParamDefault::Value(v, text) => Some((p.name, text, v)),
235                    _ => None,
236                })
237                .collect();
238            let get = |name: &str| shown.iter().find(|(n, _, _)| *n == name).cloned().unwrap();
239            for (name, value) in [
240                ("var_degree", json!(ldpc::DEFAULT_VAR_DEGREE)),
241                ("seed", json!(ldpc::DEFAULT_PEG_SEED)),
242                ("rule", json!(ldpc::DEFAULT_RULE.name())),
243                ("alpha", json!(ldpc::DEFAULT_ALPHA)),
244                ("layered", json!(ldpc::DEFAULT_LAYERED)),
245                ("iterations", json!(ldpc::DEFAULT_MAX_ITERATIONS)),
246            ] {
247                let (_, text, v) = get(name);
248                assert_eq!(v, value, "{name}");
249                // the documented text is the value
250                assert_eq!(text, value.as_str().map_or_else(|| value.to_string(), str::to_string), "{name}");
251            }
252        }
253        let q = LdpcSpec::parse("ldpc code", json!({"n": 128, "k": 64})).unwrap().settings;
254        assert_eq!(
255            (q.var_degree, q.seed, q.rule.as_str()),
256            (ldpc::DEFAULT_VAR_DEGREE, ldpc::DEFAULT_PEG_SEED, "sum_product")
257        );
258        assert_eq!(
259            (q.alpha, q.layered, q.iterations),
260            (ldpc::DEFAULT_ALPHA, ldpc::DEFAULT_LAYERED, ldpc::DEFAULT_MAX_ITERATIONS)
261        );
262    }
263}
comnum_spec/blocks/coding/codes.rs

comnum_spec/blocks/coding/
codes.rs
