On the concatenated structure of a linear code (Q1277245)

Let \(F_q\) be a finite field with \(q\) elements and denote by \(C(n,k,d)\) a linear code of length \(n\) over \(F_q\) of dimension \(k\) and minimum distance \(d\). Define \(B(n_B,k_B,d_B)\) over \(F_q\) to be an inner code, \(E(n_E,k_E,d_E)\) over \(F_{q^{k_B}}\) to be an outer code and \({\mathcal C}\) to be the concatenateed code, obtained by replacing the elements of \(F_{q^{k_B}}\) by codewords of \(B\) according to a map \(\Theta\) from \((F_{q^{k_B}})^{n_E}\) to \(B^{n_E}\). The problem considered here is to determine a concatenated structure of a linear code, given its generating matrix, i.e. determine the inner and outer codes, if they exist. In section 3 of the paper, three steps are given for recovering the concatenated structure of the code: (i) The support of the code is partitioned in a number of blocks, called inner blocks and the restriction of \({\mathcal C}\) to any one of these blocks is equal to the inner code. The inner blocks and a generating matrix of the inner code are recovered by using the properties of the dual of a concatenated code. (ii) The inner blocks are reordered by finding a permutation between two small equivalent binary codes. (iii) A particular generating matrix is found and used to recover a generating matrix of the outer code. Section 4 of the paper describes an implementation of the entire procedure and gives comments on its algorithmic complexity.