Abstract
We prove new lower bounds on the rate of codes for noisy multiple access adder channel and discuss its application to the well-known coin weighing problem in the case when some measurements are incorrect.
Similar content being viewed by others
References
Gyorfi L., Gyori S., Laczay B., Ruszinko M.: Lectures on multiple access channels. http://www.szit.bme.hu/~gyori/AFOSR-05/book.pdf.
Gritsenko V., Kabatiansky G., Lebedev V., Maevskiy A.: Oncodes for multiple access adder channel with noise and feedback. In: Proceedings of the Ninth International Workshop on Coding and Cryptography (WCC-2015), Paris (2015).
Erdos P., Renyi A.: On two problems of information theory. Publ. Math. Inst. Hung. Acad. Sci. 8, 241–254 (1963).
Lindstrom B.: On a combinatorial detection problem, I. Publ. Math. Inst. Hung. Acad. Sci. 9, 195–207 (1964).
Cantor D., Mills W.: Determining a subset from a certain combinatorial properties. Can. J. Math. 18, 42–48 (1966).
Chang S.C., Weldon E.J.: Coding for \(T\)-user multiple access channels. IEEE Trans. Inf. Theory 25(6), 684–691 (1979).
Harary F., Meter R.: On the metric dimension of a graph. Ars Comb. 2, 191–195 (1976).
Slatter P.: Leaves on trees. Cong. Numer. 14, 549–599 (1975).
Kabatianski G., Lebedev V., Thorpe J.: The Mastermind game andthe rigidity of the Hamming space. In: Proceedings on IEEE International Symposium on Information Theory, Sorrento (2000).
Lindstrom B.: On \(B_{2}\)-sequences of vectors. J. Number Theory 4, 261–265 (1972).
Cohen G., Litsyn S., Zemor G.: Binary B2-sequences: a new upper bound. J. Comb. Theory Ser. A 94(1), 152155 (2001).
Gargano L., Montuori V., Setaro G., Vacaro U.: An improved algorithm for quantative group testing. Discret. Appl. Math. 36, 299306 (1992).
MacWilliams F.J., Sloane N.J.A.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam (1977).
Dyachkov A.A., Rykov V.V.: On a coding model for a multiple-access adder channel. Probl. Inf. Trans. 17(2), 94–104 (1981).
Poltyrev G.S.: Improved upper bound on the probability of decoding error for codes of complex structure. Probl. Inf. Trans. 23(4), 251–262 (1987).
Cheng J., Watanabe Y.: A multiuser \(k\)-ary codes for the noisy multiple-access adder channel. IEEE Trans. Inf. Theory 47(6), 2603–2607 (2001).
Khachatryan G.G.: \(\sigma \)-decodable code construiction for a \(T\)-user adder channel. Probl. Inf. Trans. 24(2), 159–163 (1988).
Malyutov M.: Search for sparse active inputs: a review. Inf. Theory Comb. Search Theory 7777, 609–647 (2014).
Bshouty N.H., Mazzawi H.: Algorithms for the coin weighing problem with the presence of noise. Electron. Colloq. Comput. Complex. Rep. 18, 124 (2011).
Donoho D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289–1306 (2006).
Candes E.J., Tao T.: Near-optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inform. Theory 52(4), 5406–5425 (2006).
Vladuts S.G., Kabatiansky G.A., Lomakov V.V.: On error-correction under distortions in channel and syndrom. Probl. Inf. Trans. 52(2), 132–138 (2015).
Ulam S.M.: Adventures of Mathematician. Scribner’s, New York (1976).
Pelc A.: Solution of Ulam’s problem on searching with a lie. J. Comb. Theory Ser. A 44, 129–140 (1987).
Yekhanin S., Dumer I.: Long nonbinary codes exceeding the Gilbert Varshamov bound for any fixed distance. IEEE Trans. Inf. Theory 50(10), 2357–2362 (2004).
Acknowledgments
The research was carried out at the IITP RAS and supported by the Russian Science Foundation (project 14-50-00150).
Author information
Authors and Affiliations
Corresponding author
Additional information
This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Coding and Cryptography”.
Rights and permissions
About this article
Cite this article
Gritsenko, V., Kabatiansky, G., Lebedev, V. et al. Signature codes for noisy multiple access adder channel. Des. Codes Cryptogr. 82, 293–299 (2017). https://doi.org/10.1007/s10623-016-0228-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-016-0228-1