scientific article; zbMATH DE number 1498801
Soft-decision maximum-likelihood decoding algorithms are studied that try to find an error-free information subset in a number of random-search trials. The problem of such decoding is much different from that for minimum distance decoding. It is stated that the main problem is as follows: For every ellipsoid \[ E(v,r)= \Big\{s\in E^n_2 \Bigm|\sum_{j} v_js_j^2\leq r\Big\} \] of exponential size \(2^{n-k}\), design a minimum sphero-ellipsoidal covering \(T\bigl(n,n-k,E(v,r)\bigr)\) that takes the least possible number of vectors from the sphere \(S(n,n-k)\) to cover all vectors included in \(E(v,r)\). It turns out that any such covering \(T\bigl(n,n-k,E(v,r)\bigr)\) has size \(|T|\) upper-bounded by the order \(L_0=C_n^{D}/C_{n-k}^{D}.\) Most ellipsoids need exponentially smaller coverings, so that the spherical covering gives the worst case. The following theorem shows that the lower and upper bounds have the same exponential order: Theorem 1. Every ellipsoid \(E(v,r)\) of exponential size \(2^{n-k}\) can be covered by \(T\) randomly chosen vectors of Hamming weight \(n-k\), where \[ \log_2 T\preceq n(1-R)\bigl(1-H(\delta /(1-R))\bigr), \quad n\to \infty. \] So, for virtually all linear binary \((n,k)\)-codes used on any memoryless channel, the maximum-likelihood decoding complexity is upper-bounded by exponential order \(2^{nc}\), where \(c=\)\break \((1-R)\bigl(1-H(\delta /(1-R))\bigr)\). Theorem 2. For every ellipsoid \(E(v,r)\) of exponential size \(2^{n-k}\), the minimum covering size \(\bigl|T_{\min} (n,n-k,E(v,r))\bigr|\) is bounded from below by \[ \log_2 \bigl|T_{\min} (n,n-k,E(v,r))\bigr|\succeq \min_{\{\beta_1,\dots,\beta_n\}} \Bigl\{n-k-\sum_{j=1}^{n}\beta _{j} H(p_{j}/\beta _{j})\Bigr\} \] subject to the constraints \(\beta _1+\dots+\beta _n=n-k\), \(\beta _j \geq 2p_j\), as \(n\to \infty\). For the entire collection see [Zbl 0918.00043].
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4500992)
