Double and Triple Node-Erasure-Correcting Codes over Complete Graphs

Lev Yohananov, Yuval Efron, Eitan Yaakobi

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

תקציר

In this paper we study array-based codes over graphs for correcting multiple node failures. These codes have applications to neural networks, associative memories, and distributed storage systems. We assume that the information is stored on the edges of a complete undirected graph and a node failure is the event where all the edges in the neighborhood of a given node have been erased. A code over graphs is called ρ-node-erasure-correcting if it allows to reconstruct the erased edges upon the failure of any ρ nodes or less. We present a binary optimal construction for double-node-erasure correction together with an efficient decoding algorithm, when the number of nodes is a prime number. Furthermore, we extend this construction for triple-node-erasure-correcting codes when the number of nodes is a prime number and two is a primitive element in mathbb Z n. These codes are at most a single bit away from optimality.

שפה מקוריתאנגלית אמריקאית
מספר המאמר8985404
עמודים (מ-עד)4089-4103
מספר עמודים15
כתב עתIEEE Transactions on Information Theory
כרך66
מספר גיליון7
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 יולי 2020

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1710???
  • ???subjectarea.asjc.1700.1706???
  • ???subjectarea.asjc.3300.3309???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Double and Triple Node-Erasure-Correcting Codes over Complete Graphs'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי