Algebraic Coding Theory and Applications
Type
conference contribution
Date Issued
2024-08-19
Author(s)
Abstract
In mathematics, coding theory plays the main role in designing error-resistant
codes, allowing secure and accurate data transmission in telecommunications. Moreover, codes are used to repair failures inside digital storage systems as well as to build post-quantum cryptographic schemes. In the theory of error-correcting codes, there exists three main currents of work: block codes, convolutional codes and sub space codes.
The classical type of codes to correct errors during data transmission via some communication channel have been linear block codes. An (n, k) linear block code C is defined as a k dimensional subspace of the vector space Fqn over some finite field Fq . The parameter n is called the length of the code. Hence, there exists a matrix G ∈ Fqk×n, called generator matrix of C, such that C = {uG, u ∈ Fkq }.
Convolutional codes are a generalization of linear block codes to the polynomial setting. An (n, k) convolutional code is defined as a Fq [z]-submodule with rank k of the module Fq [z]n. Thus, for an (n, k) convolutional code C, there exists some polynomial generator matrix G(z) ∈ Fq [z]k×n such that C = {u(z)G(z), u(z) ∈ Fq [z]k}. As the codewords of a convolutional code can be obtained via polynomial multiplication, they possess a convolutional structure, which makes them very suitable for sequential encoding and decoding. Consequently, they are very useful for application in streaming systems where the acceptable delay is rather tight. Since the codewords of a convolutional code are polynomial vectors, they possess a third code parameter called the degree δ of the code. It is defined as the largest degree
of all the full-size minors of any generator matrix G(z) of C. One then speaks of an (n, k, δ) convolutional code. A convolutional code of degree δ = 0 is nothing else than a linear block code.
Subspace codes are defined as sets of subsets of Fqn. In this approach, the codewords of the subspace code are themselves subspaces. This family serves as an efficient means to represent and transmit information reliably. Essentially, instead of individual vectors, the subspace code encodes information using entire subspaces, providing a framework for robust data transmission and storage in various applications, like e.g. network coding.
The space in which a code is constructed is endowed with a metric that gives
us a weight (wt(·)) for the codewords and distances between them and thus allows us to define the minimum distance of a code, which is a measure for the number of errors this code can correct. For linear codes this minimum distance is equal to dmin(C) = min{wt(v)|v ∈ C, v̸ = 0}. In classical coding theory the Hamming distance is used, that is, the amount of elements in which two codewords differ.
Nevertheless, coding theory has been developed by using other metrics such as subspace distance, Rank distance, Lee distance or chinese euclidean distance. For the last two of these distances, one considers Zpn instead of Fqn as ambient space, i.e. one is working over finite rings instead of finite fields.
For convolutional codes, such distance measures can be extended via wt(v(z))=SUM_{t=0}^deg(v(z)) wt(vt) for the polynomial v(z) = SUM_{t=0}^deg(v(z)) vtzt ∈ Fq [z]n. Moreover, for these codes, one has two main distance measures, namely the free distance dfree(C) = min{wt(v(z))|v(z) ∈ C, v(z) not= 0} and the j-th column distance dcj(C) := min{wt(v[0,j](z)) | v(z) ∈ C and v0 not= 0 where v[0,j](z) = v0 + v1z + · · · + vj zj for j ∈ N0}. The second is used if one wants to measure just the number of errors that
can be corrected with time-delay j.
When constructing codes it is desirable to do it in an optimal way depending on what feature we want to explode. There exist different bounds for different features, some of them (among many other bounds) are the (generalised) Singleton bound for the minimum distance or the Gilbert-Varshamov and Sphere-packing bounds for the amount of codewords in a code. From the error-correcting capacity point of view, codes that hold bounds on distances are of special interest. Those which have maximum free or minimum distance are called Maximum Distance Separable (MDS) and those which achieve the maximum possible column distances are named
Maximum Distance Profile (MDP).
An important value that is related with the amount of codewords in a code, as well as the Gilbert-Varshamov and Sphere-packing bounds previously mentioned, is the covering radius, that is, the minimum natural number r such that every element of the space is contained in at least one ball of radius r centered at each codeword of the code. This value gives an idea on how the elements of the code are spread over the space.
Coding theory has various relations to algebra and combinatorics. For the construction of good codes, amongst others, finite geometry and design theory as well as group theory have been used. This is in particular true for LDPC codes, which are defined as codes where C = {v ∈ Fn
q | Hv⊤ = 0} with a sparse matrix H ∈ Fq(n−k)×n. In a similar way also LDPC convolutional codes can be defined. These codes became important for applications, for error-correction as well as for the development of code-based cryptosystems, as they come with efficient decoding algorithms, like
the bit-flipping algorithm.
codes, allowing secure and accurate data transmission in telecommunications. Moreover, codes are used to repair failures inside digital storage systems as well as to build post-quantum cryptographic schemes. In the theory of error-correcting codes, there exists three main currents of work: block codes, convolutional codes and sub space codes.
The classical type of codes to correct errors during data transmission via some communication channel have been linear block codes. An (n, k) linear block code C is defined as a k dimensional subspace of the vector space Fqn over some finite field Fq . The parameter n is called the length of the code. Hence, there exists a matrix G ∈ Fqk×n, called generator matrix of C, such that C = {uG, u ∈ Fkq }.
Convolutional codes are a generalization of linear block codes to the polynomial setting. An (n, k) convolutional code is defined as a Fq [z]-submodule with rank k of the module Fq [z]n. Thus, for an (n, k) convolutional code C, there exists some polynomial generator matrix G(z) ∈ Fq [z]k×n such that C = {u(z)G(z), u(z) ∈ Fq [z]k}. As the codewords of a convolutional code can be obtained via polynomial multiplication, they possess a convolutional structure, which makes them very suitable for sequential encoding and decoding. Consequently, they are very useful for application in streaming systems where the acceptable delay is rather tight. Since the codewords of a convolutional code are polynomial vectors, they possess a third code parameter called the degree δ of the code. It is defined as the largest degree
of all the full-size minors of any generator matrix G(z) of C. One then speaks of an (n, k, δ) convolutional code. A convolutional code of degree δ = 0 is nothing else than a linear block code.
Subspace codes are defined as sets of subsets of Fqn. In this approach, the codewords of the subspace code are themselves subspaces. This family serves as an efficient means to represent and transmit information reliably. Essentially, instead of individual vectors, the subspace code encodes information using entire subspaces, providing a framework for robust data transmission and storage in various applications, like e.g. network coding.
The space in which a code is constructed is endowed with a metric that gives
us a weight (wt(·)) for the codewords and distances between them and thus allows us to define the minimum distance of a code, which is a measure for the number of errors this code can correct. For linear codes this minimum distance is equal to dmin(C) = min{wt(v)|v ∈ C, v̸ = 0}. In classical coding theory the Hamming distance is used, that is, the amount of elements in which two codewords differ.
Nevertheless, coding theory has been developed by using other metrics such as subspace distance, Rank distance, Lee distance or chinese euclidean distance. For the last two of these distances, one considers Zpn instead of Fqn as ambient space, i.e. one is working over finite rings instead of finite fields.
For convolutional codes, such distance measures can be extended via wt(v(z))=SUM_{t=0}^deg(v(z)) wt(vt) for the polynomial v(z) = SUM_{t=0}^deg(v(z)) vtzt ∈ Fq [z]n. Moreover, for these codes, one has two main distance measures, namely the free distance dfree(C) = min{wt(v(z))|v(z) ∈ C, v(z) not= 0} and the j-th column distance dcj(C) := min{wt(v[0,j](z)) | v(z) ∈ C and v0 not= 0 where v[0,j](z) = v0 + v1z + · · · + vj zj for j ∈ N0}. The second is used if one wants to measure just the number of errors that
can be corrected with time-delay j.
When constructing codes it is desirable to do it in an optimal way depending on what feature we want to explode. There exist different bounds for different features, some of them (among many other bounds) are the (generalised) Singleton bound for the minimum distance or the Gilbert-Varshamov and Sphere-packing bounds for the amount of codewords in a code. From the error-correcting capacity point of view, codes that hold bounds on distances are of special interest. Those which have maximum free or minimum distance are called Maximum Distance Separable (MDS) and those which achieve the maximum possible column distances are named
Maximum Distance Profile (MDP).
An important value that is related with the amount of codewords in a code, as well as the Gilbert-Varshamov and Sphere-packing bounds previously mentioned, is the covering radius, that is, the minimum natural number r such that every element of the space is contained in at least one ball of radius r centered at each codeword of the code. This value gives an idea on how the elements of the code are spread over the space.
Coding theory has various relations to algebra and combinatorics. For the construction of good codes, amongst others, finite geometry and design theory as well as group theory have been used. This is in particular true for LDPC codes, which are defined as codes where C = {v ∈ Fn
q | Hv⊤ = 0} with a sparse matrix H ∈ Fq(n−k)×n. In a similar way also LDPC convolutional codes can be defined. These codes became important for applications, for error-correction as well as for the development of code-based cryptosystems, as they come with efficient decoding algorithms, like
the bit-flipping algorithm.
Language
English
HSG Classification
contribution to scientific community
Event Title
26th International Symposium on Mathematical Theory of Networks and Systems
Event Location
Cambridge, United Kingdom
Event Date
19-23 August, 2024
Official URL
File(s)![Thumbnail Image]()
Name
Session_proposal_MTNS_2024.pdf
Size
142.04 KB
Format
Adobe PDF
Checksum (MD5)
c2965f2ba73835dc9aa69013228f3987