Jeudi 7 mai 2015 à 10h30 en salle C48
Buket Özkaya (Télécom ParisTech)
Titre : Multidimensional Quasi-Cyclic and Convolutional Codes
Résumé :
For m, l integers with gcd(m, q) = 1, a quasi-cyclic (QC) code of length ml and index l over F_q is a linear code C ⊂ F_q^ml which is invariant under the shift of codewords by l positions (where l is the minimal such number).
It is well-known that such a QC code can be viewed algebraically as an R-module of R^l, where R = F_q[x]/(x^m -1).
Alternatively, we can let S = F_q[x, y]/(x^m -1, y^l -1) and view a QC code of length ml and index l as an R-submodule of S.
One can decompose a QC code over F_q into its constituent codes, which are linear codes over certain extensions of F_q.
Also, a concatenated decomposition structure can be described for QC codes where the inner codes in the decomposition are minimal cyclic codes.
It has been shown that the constituents in the sense of Ling-Solé and the outer codes in the concatenated structure given by Jensen are the same.
We define multidimensional generalizations of QC codes and investigate their properties.
For n ≥ 1, we let R_n = F_q[x_1, x_2, ... , x_n]/(x_1^(m_1) - 1, ... , x_n^(m_n) - 1)
and define the QnDC code of size m_1 x ... x m_(n+1) as an R_n -submodule of R_(n+1).
It is clear the for n = 1, we obtain QC codes (of length m_1m_2 and index m_2 ).
QnDC codes are linear codes of length m_1 ... m_(n+1) over F_q and they can also be viewed as QC codes of index l = m_2 ... m_(n+1).
However, they have extra shift-invariance properties than ordinary QC codes.
Being QC codes, we can talk about the decomposition of QnDC codes into constituents (or the concatenated structure).
We prove that the constituents (or the outer codes in Jensen’s concatenated decomposition) of a length m_1 ... m_(n+1) QnDC code are Q(n − 1)DC codes (over various extensions of F_q) of length m_2 ... m_(n+1).
We also prove that the family of QnDC codes are asymptotically good for any n ≥ 1.
Quasi-cyclic codes are naturally related to convolutional codes which are defined as rank k F_q[x]-submodules of F_q[x]^l.
Free distance of a convolutional code can be lower bounded by the minimum distance of an associated QC code.
Multidimensional generalizations of convolutional codes have also been introduced and studied.
We show that one can naturally associate a QnDC code to any nD convolutional code and prove an analogue of Lally’s result for a particular class of 2D convolutional codes.
Along the way, an alternative new description of noncatastrophic polynomial encoders is given for 1-generator 1D convolutional codes and a sufficient condition for noncatastrophic nD polynomial encoders is obtained for 1-generator nD convolutional codes.