Standard Lengthening for NRT-Codes

If an [s, n, d]-code C0 contains an [s, n−1, d + 1]-subcode C1 (as it is the case for Reed-Solomon codes, algebraic-geometric codes and other families of codes), C0 can be lengthened to an [s + 1, n, d + 1]-code C. If G0 is a generator matrix of C0 such that the first n−1 rows of G0 are a generator matrix of C1, a generator matrix of C is given by

G := $\displaystyle \left(\vphantom{\vec{G}_{0}\begin{array}{c} 0\\ \vdots\\ 0\\ 1\end{array}}\right.$G0$\displaystyle \begin{array}{c} 0\\ \vdots\\ 0\\ 1\end{array}$$\displaystyle \left.\vphantom{\vec{G}_{0}\begin{array}{c} 0\\ \vdots\\ 0\\ 1\end{array}}\right)$.

The same result can be obtained by applying construction X to C1C0 with the [1, 1, 1]-code without redundancy.

For NRT-codes with depth T > 1 and n > 1 a similar construction is possible. Let C0 denote a linear [(s, T ), n, d0]-code. Let T ʹ := min{T , n} and let C0 contain a chain of subcodes Ci for i = 1,…, T ʹ−1 with CTʹ−1 ⊂ ⋯ ⊂ C1C0, dimensions dimCi = ni, and minimum distances d (Ci) = di. Furthermore assume that G0 denote a generator matrix of C0 such that the first ni rows of G form a generator matrix of Ci. Then C0 can be lengthened to an [(s + 1, T ), n, d]-code with

d = $\displaystyle \min_{{i=0,\ldots,Tʹ−1}}^{}$di + i

and generator matrix

G := $\displaystyle \left(\vphantom{\vec{G}_{0} \middle\vert \begin{array}{c} \vec{0}_{(n-T)\times T}\\ \vec{I}_{T}\end{array}}\right.$G0 $\displaystyle \middle$$\displaystyle \begin{array}{c} \vec{0}_{(n-T)\times T}\\ \vec{I}_{T}\end{array}$$\displaystyle \left.\vphantom{\vec{G}_{0} \middle\vert \begin{array}{c} \vec{0}_{(n-T)\times T}\\ \vec{I}_{T}\end{array}}\right)$

for nT and

G := $\displaystyle \left(\vphantom{\vec{G}_{0} \middle\vert \vec{0}_{n\times(T-n)}\vec{I}_{n}}\right.$G0 $\displaystyle \middle$|  0n×(T-n)In$\displaystyle \left.\vphantom{\vec{G}_{0} \middle\vert \vec{0}_{n\times(T-n)}\vec{I}_{n}}\right)$

for nT .

Note that this result cannot be obtained using construction X in a straightforward way! It is only possible because the extension code Ce defined by the generator matrix I is an unequal error protection (UEP) NRT-code: If Di denotes the code defined by the first i rows of I, then d (Ce ∖ Di) = i + 1 for i = 0,…, T ʹ−1 (cf. [1]).


[1]Jürgen Bierbrauer, Yves Edel, and Ludo Tolhuizen.
New codes via the lengthening of BCH codes with UEP codes.
Finite Fields and Their Applications, 5(4):345–353, October 1999.
doi:10.1006/ffta.1999.0245 MR1711841 (2000j:94027)


Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.
Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Standard Lengthening for NRT-Codes.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2008-04-04.

Show usage of this method