Johnson graph codes

Iwan Duursma, Xiao Li

Research output: Contribution to journalArticlepeer-review

Abstract

Array codes are the preferred codes for distributed storage, such that different rows in an array are stored at different nodes. Layered codes use a sparse format for stored arrays with a single parity check per column and no other parity checks. Remarkably, the simple structure of layered codes is optimal when data is collected from all but one node. Codes that collect data from fewer nodes include improved layered codes, determinant codes, cascade codes and moulin codes. As our main result we show that the concatenation of layered codes with suitable outer codes achieves the performance of cascade and moulin codes which is conjectured to be optimal for general regenerating codes. The codes that we use as outer codes are in a new class of codes that we call Johnson graph codes. The codes have properties similar to those of Reed–Muller codes. In both cases the topological structure of the set of coordinates can be used to identify information sets and codewords of small weight.

Original languageEnglish (US)
JournalDesigns, Codes, and Cryptography
DOIs
StateAccepted/In press - 2022

Keywords

  • Algebraic coding theory
  • Codes for distributed storage
  • Determinants
  • Johnson graph
  • Multilinear algebra
  • Regenerating codes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Johnson graph codes'. Together they form a unique fingerprint.

Cite this