×

Signature codes for noisy multiple access adder channel. (English) Zbl 1402.94040

Summary: 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.

MSC:

94A15 Information theory (general)
05D05 Extremal set theory
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gyorfi L., Gyori S., Laczay B., Ruszinko M.: Lectures on multiple access channels. http://www.szit.bme.hu/ gyori/AFOSR-05/book.pdf.
[2] 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). · Zbl 1402.94040
[3] Erdos P., Renyi A.: On two problems of information theory. Publ. Math. Inst. Hung. Acad. Sci. 8, 241-254 (1963). · Zbl 0119.34001
[4] Lindstrom B.: On a combinatorial detection problem, I. Publ. Math. Inst. Hung. Acad. Sci. 9, 195-207 (1964). · Zbl 0154.44005
[5] Cantor D., Mills W.: Determining a subset from a certain combinatorial properties. Can. J. Math. 18, 42-48 (1966). · Zbl 0201.33802
[6] Chang S.C., Weldon E.J.: Coding for \[T\] T-user multiple access channels. IEEE Trans. Inf. Theory 25(6), 684-691 (1979). · Zbl 0423.94007
[7] Harary F., Meter R.: On the metric dimension of a graph. Ars Comb. 2, 191-195 (1976). · Zbl 0349.05118
[8] Slatter P.: Leaves on trees. Cong. Numer. 14, 549-599 (1975).
[9] 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).
[10] Lindstrom B.: On \[B_2\] B2-sequences of vectors. J. Number Theory 4, 261-265 (1972). · Zbl 0235.10028
[11] Cohen G., Litsyn S., Zemor G.: Binary B2-sequences: a new upper bound. J. Comb. Theory Ser. A 94(1), 152155 (2001). · Zbl 0986.11014
[12] Gargano L., Montuori V., Setaro G., Vacaro U.: An improved algorithm for quantative group testing. Discret. Appl. Math. 36, 299306 (1992). · Zbl 0761.68071
[13] MacWilliams F.J., Sloane N.J.A.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam (1977). · Zbl 0369.94008
[14] Dyachkov A.A., Rykov V.V.: On a coding model for a multiple-access adder channel. Probl. Inf. Trans. 17(2), 94-104 (1981). · Zbl 0481.94003
[15] 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). · Zbl 0659.94016
[16] Cheng J., Watanabe Y.: A multiuser \[k\] k-ary codes for the noisy multiple-access adder channel. IEEE Trans. Inf. Theory 47(6), 2603-2607 (2001). · Zbl 0999.94023
[17] Khachatryan G.G.: \[ \sigma\] σ-decodable code construiction for a \[T\] T-user adder channel. Probl. Inf. Trans. 24(2), 159-163 (1988). · Zbl 0666.94007
[18] Malyutov M.: Search for sparse active inputs: a review. Inf. Theory Comb. Search Theory 7777, 609-647 (2014). · Zbl 1309.94018
[19] Bshouty N.H., Mazzawi H.: Algorithms for the coin weighing problem with the presence of noise. Electron. Colloq. Comput. Complex. Rep. 18, 124 (2011). · Zbl 1209.68267
[20] Donoho D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289-1306 (2006). · Zbl 1288.94016
[21] Candes E.J., Tao T.: Near-optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inform. Theory 52(4), 5406-5425 (2006). · Zbl 1309.94033
[22] 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). · Zbl 1339.94087
[23] Ulam S.M.: Adventures of Mathematician. Scribner’s, New York (1976). · Zbl 0352.01009
[24] Pelc A.: Solution of Ulam’s problem on searching with a lie. J. Comb. Theory Ser. A 44, 129-140 (1987). · Zbl 0621.68056
[25] 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). · Zbl 1283.94148
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.