Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 1-2/2017

16-09-2016

Symmetric disjunctive list-decoding codes

Authors: A. G. D’yachkov, I. V. Vorobyev, N. A. Polyanskii, V. Yu. Shchukin

Published in: Designs, Codes and Cryptography | Issue 1-2/2017

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this work, we consider symmetric disjunctive list-decoding (SLD) codes, which are a class of binary codes based on a symmetric disjunctive sum (SDS) of binary symbols. By definition, the SDS takes values from the ternary alphabet \(\{0, 1, *\}\), where the symbol \(*\) denotes “erasure”. Namely: SDS is equal to 0 (1) if all its binary symbols are equal to 0 (1), otherwise SDS is equal to \(*\). The main purpose of this work is to obtain bounds on the rate of these codes.
previous article Cover-free codes and separating system codes
next article Almost cover-free codes and designs
Footnotes
1
The adaptive symmetric group testing for the search of binomial sample was considered in [21].
 
Literature
1.
2.
Cohen G.D., Schaathun H.G.: Asymptotic overview on separating codes. Technical Report 248, Department of Informatics, University of Bergen, Norway (2003).
3.
Csiszar I., Korner J.: Information Theory: Coding Theorems for Discrete Memoryless Systems. Cambridge University Press, Cambridge (2011).CrossRefMATH
4.
D’yachkov A.G.: Lectures on Designing Screening Experiments. Lecture Note Series 10, Combinatorial and Computational Mathematics Center, Pohang University of Science and Technology (POSTECH), Korea Republic (2003).
5.
D’yachkov A.G., Rykov V.V.: An application of codes for the multiple access channel in the ALOHA communication system. In: Proccedings of the 6-th All-Union Seminar in Computing Networks, vol. 4, pp. 18–24. Moscow-Vinnitsa (1981) (in Russian).
6.
D’yachkov A.G., Rykov V.V.: A survey of superimposed code theory. Probl. Inf. Transm. 12(4), 229–242 (1983).MATHMathSciNet
7.
D’yachkov A.G., Rykov V.V.: Superimposed codes for multiple accessing of the OR-channel. In: Proceedings of the IEEE International Symposium on Information Theory (ISIT). IEEE, Boston (1998).
8.
D’yachkov A.G., Rykov V.V., Rashad A.M.: Superimposed distance codes. Probl. Inf. Transm. 18(4), 237–250 (1989).MATHMathSciNet
9.
D’yachkov A.G., Vorobyev I.V., Polyanskii N.A., Shchukin V.Yu.: Bounds on the rate of superimposed codes. In: Proceedings of the IEEE International Symposium on Information Theory (ISIT), pp. 2341–2345. IEEE, Honolulu (2014).
10.
D’yachkov A.G., Vorobyev I.V., Polyanskii N.A., Shchukin V.Yu.: Bounds on the rate of disjunctive codes. Probl. Inf. Transm. 50(1), 27–56 (2014).
11.
D’yachkov A.G., Vorobyev I.V., Polyanskii N.A., Shchukin V.Yu.: Symmetric disjunctive list-decoding codes. In: Proceedings of the IEEE International Symposium on Information Theory (ISIT), pp. 2236–2240. IEEE, Hong Kong (2015).
12.
D’yachkov A.G., Vorobyev I.V., Polyanskii N.A., Shchukin V.Yu.: Almost disjunctive list-decoding codes. Probl. Inf. Transm. 51(2), 110–131 (2015).
13.
Friedman A.D., Graham R.L., Ullman J.D.: Universal single transition time asynchronous state assignments. IEEE Trans. Comput. 18(6), 541–547 (1969).CrossRef
14.
Galeev E.M., Tikhomirov V.M.: Optimization: Theory, Examples, Problems. Editorial URSS, Moscow (2000) (in Russian).
15.
Kautz W.H., Singleton R.C.: Nonrandom binary superimposed codes. IEEE Trans. Inf. Theory. 10(4), 363–377 (1964).CrossRefMATH
16.
17.
18.
Shchukin V.Yu.: List Decoding for a multiple-access hyperchannel. Probl. Inf. Transm. (will be published).
19.
20.
Sholomov L.A.: Binary representations of underdetermined data and superimposed codes. Appl. Discret. Math. 1, 17–33 (2013) (in Russian).
21.
Sobel M., Kumar S., Blumenthal S.: Symmetric binomial group-testing with three outcomes. In: Proceedings the Symposium on Statistical Decision Theory and Related Topics, pp. 119–160. Purdue University, Lafayette (1971).
22.
Vilenkin P.A.: On constructions of list-decoding superimposed codes. In: Proceedings of the 6th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT-6), pp. 228–231. Pskov, Russia (1998).
Metadata
Title
Symmetric disjunctive list-decoding codes
Authors
A. G. D’yachkov
I. V. Vorobyev
N. A. Polyanskii
V. Yu. Shchukin
Publication date
16-09-2016
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 1-2/2017
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-016-0278-4

Other articles of this Issue 1-2/2017

Designs, Codes and Cryptography 1-2/2017 Go to the issue

OriginalPaper

Antiderivative functions over

OriginalPaper

Security proof of the canonical form of self-synchronizing stream ciphers

OriginalPaper

A code-based group signature scheme

OriginalPaper

Lower bound of covering radius of binary irreducible Goppa codes

OriginalPaper

Almost cover-free codes and designs

OriginalPaper

Algebraic decoding of folded Gabidulin codes

Premium Partner

    Image Credits