On the Minimum Distance of Subspace Codes Generated by Linear Cellular Automata

Luca Mariot; Federico Mazzone

doi:10.1007/978-3-031-42250-8_8

On the Minimum Distance of Subspace Codes Generated by Linear Cellular Automata

Luca Mariot^*, Federico Mazzone

^*Corresponding author for this work

Semantics, Cybersecurity & Services

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

19 Downloads (Pure)

Abstract

Motivated by applications to noncoherent network coding, we study subspace codes defined by sets of linear cellular automata (CA). As a first remark, we show that a family of linear CA where the local rules have the same diameter—and thus the associated polynomials have the same degree—induces a Grassmannian code. Then, we prove that the minimum distance of such a code is determined by the maximum degree occurring among the pairwise greatest common divisors (GCD) of the polynomials in the family. Finally, we consider the setting where all such polynomials have the same GCD, and determine the cardinality of the corresponding Grassmannian code. As a particular case, we show that if all polynomials in the family are pairwise coprime, the resulting Grassmannian code has the highest minimum distance possible.

Original language	English
Title of host publication	Cellular Automata and Discrete Complex Systems - 29th IFIP WG 1.5 International Workshop, AUTOMATA 2023, Trieste, Italy, August 30 - September 1, 2023, Proceedings
Subtitle of host publication	29th IFIP WG 1.5 International Workshop, AUTOMATA 2023, Trieste, Italy, August 30 – September 1, 2023, Proceedings
Editors	Luca Manzoni, Luca Mariot, Dipanwita Roy Chowdhury
Place of Publication	Cham
Publisher	Springer
Pages	105-119
Number of pages	15
ISBN (Electronic)	978-3-031-42250-8
ISBN (Print)	978-3-031-42249-2
DOIs	https://doi.org/10.1007/978-3-031-42250-8_8
Publication status	Published - 2023
Event	29th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2023 - Trieste, Italy Duration: 30 Aug 2023 → 1 Sept 2023 Conference number: 29

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	14152
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	29th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2023
Abbreviated title	AUTOMATA 2023
Country/Territory	Italy
City	Trieste
Period	30/08/23 → 1/09/23

Keywords

Cellular automata
Finite field
Grassmannian
Greatest common divisor
Network coding
Sylvester matrix
2024 OA procedure

Access to Document

10.1007/978-3-031-42250-8_8

ArticleFinal published version, 284 KBLicence: Taverne

Cite this

Mariot, L., & Mazzone, F. (2023). On the Minimum Distance of Subspace Codes Generated by Linear Cellular Automata. In L. Manzoni, L. Mariot, & D. Roy Chowdhury (Eds.), Cellular Automata and Discrete Complex Systems - 29th IFIP WG 1.5 International Workshop, AUTOMATA 2023, Trieste, Italy, August 30 - September 1, 2023, Proceedings: 29th IFIP WG 1.5 International Workshop, AUTOMATA 2023, Trieste, Italy, August 30 – September 1, 2023, Proceedings (pp. 105-119). (Lecture Notes in Computer Science; Vol. 14152). Springer. https://doi.org/10.1007/978-3-031-42250-8_8

Mariot, Luca ; Mazzone, Federico. / On the Minimum Distance of Subspace Codes Generated by Linear Cellular Automata. Cellular Automata and Discrete Complex Systems - 29th IFIP WG 1.5 International Workshop, AUTOMATA 2023, Trieste, Italy, August 30 - September 1, 2023, Proceedings: 29th IFIP WG 1.5 International Workshop, AUTOMATA 2023, Trieste, Italy, August 30 – September 1, 2023, Proceedings. editor / Luca Manzoni ; Luca Mariot ; Dipanwita Roy Chowdhury. Cham : Springer, 2023. pp. 105-119 (Lecture Notes in Computer Science).

@inproceedings{fe023020b72b41a49bc7bba9733b3cf2,

title = "On the Minimum Distance of Subspace Codes Generated by Linear Cellular Automata",

abstract = "Motivated by applications to noncoherent network coding, we study subspace codes defined by sets of linear cellular automata (CA). As a first remark, we show that a family of linear CA where the local rules have the same diameter—and thus the associated polynomials have the same degree—induces a Grassmannian code. Then, we prove that the minimum distance of such a code is determined by the maximum degree occurring among the pairwise greatest common divisors (GCD) of the polynomials in the family. Finally, we consider the setting where all such polynomials have the same GCD, and determine the cardinality of the corresponding Grassmannian code. As a particular case, we show that if all polynomials in the family are pairwise coprime, the resulting Grassmannian code has the highest minimum distance possible.",

keywords = "Cellular automata, Finite field, Grassmannian, Greatest common divisor, Network coding, Sylvester matrix, 2024 OA procedure",

author = "Luca Mariot and Federico Mazzone",

note = "Publisher Copyright: {\textcopyright} 2023, IFIP International Federation for Information Processing.; 29th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2023, AUTOMATA 2023 ; Conference date: 30-08-2023 Through 01-09-2023",

year = "2023",

doi = "10.1007/978-3-031-42250-8_8",

language = "English",

isbn = "978-3-031-42249-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "105--119",

editor = "Luca Manzoni and Luca Mariot and {Roy Chowdhury}, Dipanwita",

booktitle = "Cellular Automata and Discrete Complex Systems - 29th IFIP WG 1.5 International Workshop, AUTOMATA 2023, Trieste, Italy, August 30 - September 1, 2023, Proceedings",

address = "Germany",

}

Mariot, L & Mazzone, F 2023, On the Minimum Distance of Subspace Codes Generated by Linear Cellular Automata. in L Manzoni, L Mariot & D Roy Chowdhury (eds), Cellular Automata and Discrete Complex Systems - 29th IFIP WG 1.5 International Workshop, AUTOMATA 2023, Trieste, Italy, August 30 - September 1, 2023, Proceedings: 29th IFIP WG 1.5 International Workshop, AUTOMATA 2023, Trieste, Italy, August 30 – September 1, 2023, Proceedings. Lecture Notes in Computer Science, vol. 14152, Springer, Cham, pp. 105-119, 29th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2023, Trieste, Italy, 30/08/23. https://doi.org/10.1007/978-3-031-42250-8_8

On the Minimum Distance of Subspace Codes Generated by Linear Cellular Automata. / Mariot, Luca; Mazzone, Federico.
Cellular Automata and Discrete Complex Systems - 29th IFIP WG 1.5 International Workshop, AUTOMATA 2023, Trieste, Italy, August 30 - September 1, 2023, Proceedings: 29th IFIP WG 1.5 International Workshop, AUTOMATA 2023, Trieste, Italy, August 30 – September 1, 2023, Proceedings. ed. / Luca Manzoni; Luca Mariot; Dipanwita Roy Chowdhury. Cham: Springer, 2023. p. 105-119 (Lecture Notes in Computer Science; Vol. 14152).

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

TY - GEN

T1 - On the Minimum Distance of Subspace Codes Generated by Linear Cellular Automata

AU - Mariot, Luca

AU - Mazzone, Federico

N1 - Conference code: 29

PY - 2023

Y1 - 2023

N2 - Motivated by applications to noncoherent network coding, we study subspace codes defined by sets of linear cellular automata (CA). As a first remark, we show that a family of linear CA where the local rules have the same diameter—and thus the associated polynomials have the same degree—induces a Grassmannian code. Then, we prove that the minimum distance of such a code is determined by the maximum degree occurring among the pairwise greatest common divisors (GCD) of the polynomials in the family. Finally, we consider the setting where all such polynomials have the same GCD, and determine the cardinality of the corresponding Grassmannian code. As a particular case, we show that if all polynomials in the family are pairwise coprime, the resulting Grassmannian code has the highest minimum distance possible.

AB - Motivated by applications to noncoherent network coding, we study subspace codes defined by sets of linear cellular automata (CA). As a first remark, we show that a family of linear CA where the local rules have the same diameter—and thus the associated polynomials have the same degree—induces a Grassmannian code. Then, we prove that the minimum distance of such a code is determined by the maximum degree occurring among the pairwise greatest common divisors (GCD) of the polynomials in the family. Finally, we consider the setting where all such polynomials have the same GCD, and determine the cardinality of the corresponding Grassmannian code. As a particular case, we show that if all polynomials in the family are pairwise coprime, the resulting Grassmannian code has the highest minimum distance possible.

KW - Cellular automata

KW - Finite field

KW - Grassmannian

KW - Greatest common divisor

KW - Network coding

KW - Sylvester matrix

KW - 2024 OA procedure

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

U2 - 10.1007/978-3-031-42250-8_8

DO - 10.1007/978-3-031-42250-8_8

M3 - Conference contribution

AN - SCOPUS:85171591322

SN - 978-3-031-42249-2

T3 - Lecture Notes in Computer Science

SP - 105

EP - 119

BT - Cellular Automata and Discrete Complex Systems - 29th IFIP WG 1.5 International Workshop, AUTOMATA 2023, Trieste, Italy, August 30 - September 1, 2023, Proceedings

A2 - Manzoni, Luca

A2 - Mariot, Luca

A2 - Roy Chowdhury, Dipanwita

PB - Springer

CY - Cham

T2 - 29th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2023

Y2 - 30 August 2023 through 1 September 2023

ER -

Mariot L, Mazzone F. On the Minimum Distance of Subspace Codes Generated by Linear Cellular Automata. In Manzoni L, Mariot L, Roy Chowdhury D, editors, Cellular Automata and Discrete Complex Systems - 29th IFIP WG 1.5 International Workshop, AUTOMATA 2023, Trieste, Italy, August 30 - September 1, 2023, Proceedings: 29th IFIP WG 1.5 International Workshop, AUTOMATA 2023, Trieste, Italy, August 30 – September 1, 2023, Proceedings. Cham: Springer. 2023. p. 105-119. (Lecture Notes in Computer Science). doi: 10.1007/978-3-031-42250-8_8

On the Minimum Distance of Subspace Codes Generated by Linear Cellular Automata

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

On the Minimum Distance of Subspace Codes Generated by Linear Cellular Automata

Cite this