The Typical Non-Linear Code over Large Alphabets

Anina Gruica; Alberto Ravagnani

doi:10.1109/ITW48936.2021.9611444

The Typical Non-Linear Code over Large Alphabets

Anina Gruica, Alberto Ravagnani

Mathematical Communication Theory

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

Abstract

We consider the problem of describing the typical (possibly) non-linear code of minimum distance bounded from below over a large alphabet. We concentrate on block codes with the Hamming metric and on subspace codes with the injection metric. In sharp contrast with the behavior of linear block codes, we show that the typical non-linear code in the Hamming metric of cardinality q^n-d+1 is far from having minimum distance d, i.e., from being MDS. We also give more precise results about the asymptotic proportion of block codes with good distance properties within the set of codes having a certain cardinality. We then establish the analogous results for subspace codes with the injection metric, showing also an application to the theory of partial spreads in finite geometry.

Original language	English
Title of host publication	2021 IEEE Information Theory Workshop, ITW 2021 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers
ISBN (Electronic)	9781665403122
DOIs	https://doi.org/10.1109/ITW48936.2021.9611444
Publication status	Published - 2021
Event	2021 IEEE Information Theory Workshop, ITW 2021 - Virtual, Online, Japan Duration: 17 Oct 2021 → 21 Oct 2021

Conference

Conference	2021 IEEE Information Theory Workshop, ITW 2021
Country/Territory	Japan
City	Virtual, Online
Period	17/10/21 → 21/10/21

Bibliographical note

Funding Information:
The authors were partially supported by the Dutch Research Council through grant OCENW.KLEIN.539.

Publisher Copyright:
© 2021 IEEE.

Keywords

Hamming metric
Injection metric
Large alphabet
MDS code
Partial spread

Access to Document

10.1109/ITW48936.2021.9611444

https://arxiv.org/abs/2105.04378

Cite this

@inproceedings{a00641bfb6444007ab6ca0dc28f69881,

title = "The Typical Non-Linear Code over Large Alphabets",

abstract = "We consider the problem of describing the typical (possibly) non-linear code of minimum distance bounded from below over a large alphabet. We concentrate on block codes with the Hamming metric and on subspace codes with the injection metric. In sharp contrast with the behavior of linear block codes, we show that the typical non-linear code in the Hamming metric of cardinality q^n-d+1 is far from having minimum distance d, i.e., from being MDS. We also give more precise results about the asymptotic proportion of block codes with good distance properties within the set of codes having a certain cardinality. We then establish the analogous results for subspace codes with the injection metric, showing also an application to the theory of partial spreads in finite geometry.",

keywords = "Hamming metric, Injection metric, Large alphabet, MDS code, Partial spread",

author = "Anina Gruica and Alberto Ravagnani",

note = "Funding Information: The authors were partially supported by the Dutch Research Council through grant OCENW.KLEIN.539. Publisher Copyright: {\textcopyright} 2021 IEEE.; 2021 IEEE Information Theory Workshop, ITW 2021 ; Conference date: 17-10-2021 Through 21-10-2021",

year = "2021",

doi = "10.1109/ITW48936.2021.9611444",

language = "English",

booktitle = "2021 IEEE Information Theory Workshop, ITW 2021 - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

}

TY - GEN

T1 - The Typical Non-Linear Code over Large Alphabets

AU - Gruica, Anina

AU - Ravagnani, Alberto

PY - 2021

Y1 - 2021

N2 - We consider the problem of describing the typical (possibly) non-linear code of minimum distance bounded from below over a large alphabet. We concentrate on block codes with the Hamming metric and on subspace codes with the injection metric. In sharp contrast with the behavior of linear block codes, we show that the typical non-linear code in the Hamming metric of cardinality q^n-d+1 is far from having minimum distance d, i.e., from being MDS. We also give more precise results about the asymptotic proportion of block codes with good distance properties within the set of codes having a certain cardinality. We then establish the analogous results for subspace codes with the injection metric, showing also an application to the theory of partial spreads in finite geometry.

AB - We consider the problem of describing the typical (possibly) non-linear code of minimum distance bounded from below over a large alphabet. We concentrate on block codes with the Hamming metric and on subspace codes with the injection metric. In sharp contrast with the behavior of linear block codes, we show that the typical non-linear code in the Hamming metric of cardinality q^n-d+1 is far from having minimum distance d, i.e., from being MDS. We also give more precise results about the asymptotic proportion of block codes with good distance properties within the set of codes having a certain cardinality. We then establish the analogous results for subspace codes with the injection metric, showing also an application to the theory of partial spreads in finite geometry.

KW - Hamming metric

KW - Injection metric

KW - Large alphabet

KW - MDS code

KW - Partial spread

UR - http://www.scopus.com/inward/record.url?scp=85123397451&partnerID=8YFLogxK

U2 - 10.1109/ITW48936.2021.9611444

DO - 10.1109/ITW48936.2021.9611444

M3 - Conference contribution

AN - SCOPUS:85123397451

BT - 2021 IEEE Information Theory Workshop, ITW 2021 - Proceedings

PB - Institute of Electrical and Electronics Engineers

T2 - 2021 IEEE Information Theory Workshop, ITW 2021

Y2 - 17 October 2021 through 21 October 2021

ER -

The Typical Non-Linear Code over Large Alphabets

Abstract

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this