List decodability at small radii
Tóm tắt
A′(n, d, e), the smallest ℓ for which every binary error-correcting code of length n and minimum distance d is decodable with a list of size ℓ up to radius e, is determined for all d ≥ 2e − 3. As a result, A′(n, d, e) is determined for all e ≤ 4, except for 42 values of n.
Tài liệu tham khảo
Ahlswede R.: Channel capacities for list codes. J. Appl. Probab. 10(4), 824–836 (1973)
Bassalygo L.A.: New upper bounds for error-correcting codes. Problemy Peredači Informacii 1(vyp. 4), 41–44 (1965)
Blinovsky V.: Bounds for codes in the case of list decoding of finite volume. Probl. Inform. Transm. 22(1), 7–19 (1986)
Blinovsky V.: Asymptotic Combinatorial Coding Theory. The Kluwer International Series in Engineering and Computer Science, 415. Kluwer Academic Publishers, Boston (1997).
Brouwer A.E.: On the packing of quadruples without common triples. Ars Combin. 5, 3–6 (1978)
Brouwer A.E.: Optimal packings of K 4’s into a K n . J. Comb. Theory A 26(3), 278–297 (1979)
Brouwer A.E., Shearer J.B., Sloane N.J.A., Smith W.D.: A new table of constant weight codes. IEEE Trans. Inform. Theory 36(6), 1334–1380 (1990)
Cassuto Y., Bruck J.: A combinatorial bound on the list size. Technical Report, California Institute of Technology, Pasedna, CA (2004).
Elias P.: List decoding for noisy channels. Technical report 335. Research Laboratory of Electronics, Massachusetts Institute of Technology (1957).
Elias P.: Error-correcting codes for list decoding. IEEE Trans. Inform. Theory 37(1), 5–12 (1991)
Forney G.D.: Exponential error bounds for erasure, list and decision feedback schemes. IEEE Trans. Inform. Theory 14, 549–557 (1968)
Goldreich O., Levin L.A.: A hard-core predicate for all one-way functions. In: STOC 1989: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 15–17 May 1989, Seattle, Washington, USA, pp. 25–32. ACM Press (1989).
Guruswami V.: List Decoding of Error-Correcting Codes, Lecture Notes in Computer Science, vol. 3282. Springer-Verlag, Berlin (2004).
Guruswami V., Sudan M.: Extensions to the Johnson bound. Unpublished manuscript (2001).
Hanani H.: On quadruple systems. Can. J. Math. 12, 145–157 (1960)
Ji L.: Asymptotic determination of the last packing number of quadruples. Des. Codes Cryptogr. 38(1), 83–95 (2006)
Johnson S.M.: Upper bounds for constant weight error-correcting codes. Discrete Math. 3, 109–124 (1972)
Schönheim J.: On maximal systems of k-tuples. Studia Sci. Math. Hungar 1, 363–368 (1966)
Shannon C.E., Gallager R.G., Berlekamp E.R.: Lower bounds to error probability for coding on discrete memoryless channels. I. Inform. Control 10, 65–103 (1967)
Shannon C.E., Gallager R.G., Berlekamp E.R.: Lower bounds to error probability for coding on discrete memoryless channels. II. Inform. Control 10, 522–552 (1967)
Spencer J.: Maximal consistent families of triples. J. Comb. Theory 5, 1–8 (1968)
Sudan M.: Decoding of Reed Solomon codes beyond the error-correction bound. J. Complex. 13(1), 180–193 (1997)
Wozencraft J.M.: List decoding. Research Laboratory of Electronics, Massachusetts Institute of Technology, Progress report 48, pp. 90–95 (1958).
Zyablov V.V., Pinsker M.S.: List cascade decoding. Probl. Inform. Transm. 17(4), 236–240 (1982)