The Birthday Problem and Zero-Error List Codes

Parham Noorzad, Michelle Effros, Michael Langberg, Victoria Kostina

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


A key result of classical information theory states that if the rate of a randomly generated codebook is less than the mutual information between the channel's input and output, then the probability that that codebook has negligible error goes to one as the blocklength goes to infinity. In an attempt to bridge the gap between the probabilistic world of classical information theory and the combinatorial world of zero-error information theory, this work derives necessary and sufficient conditions on the rate so that the probability that a randomly generated codebook operated under list decoding (for any fixed list size) has zero error probability goes to one as the blocklength goes to infinity. Furthermore, this work extends the classical birthday problem to an information-theoretic setting, which results in the definition of a 'noisy' counterpart of Rényi entropy, analogous to how mutual information can be considered a noisy counterpart of Shannon entropy.

שפה מקוריתאנגלית
מספר המאמר9500216
עמודים (מ-עד)5791-5803
מספר עמודים13
כתב עתIEEE Transactions on Information Theory
מספר גיליון9
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - ספט׳ 2021
פורסם באופן חיצוניכן

הערה ביבליוגרפית

Publisher Copyright:
© 1963-2012 IEEE.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'The Birthday Problem and Zero-Error List Codes'. יחד הם יוצרים טביעת אצבע ייחודית.

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