nach oben

Designs, Codes and Cryptography

Erschienen in:

01.08.2015

Weighted maximum matchings and optimal equi-difference conflict-avoiding codes

verfasst von: Yuan-Hsun Lo, Hung-Lin Fu, Yi-Hean Lin

Erschienen in: Designs, Codes and Cryptography | Ausgabe 2/2015

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A conflict-avoiding code (CAC) \(\mathcal {C}\) of length \(n\) and weight \(k\) is a collection of \(k\)-subsets of \(\mathbb {Z}_n\) such that \(\varDelta (x)\cap \varDelta (y)=\emptyset \) for any \(x,y\in \mathcal {C}\) and \(x\ne y\), where \(\varDelta (x)=\{a-b:\, a,b\in x, a\ne b\}\). Let \(\text {CAC}(n,k)\) denote the class of all CACs of length \(n\) and weight \(k\). A CAC \(\mathcal {C}\in \text {CAC}(n,k)\) is said to be equi-difference if any codeword \(x\in \mathcal {C}\) has the form \(\{ 0,i,2i,\ldots , (k-1)i \}\). A CAC with maximum size is called optimal. In this paper we propose a graphical characterization of an equi-difference CAC, and then provide an infinite number of optimal equi-difference CACs for weight four.

Vorheriger Artikel New pseudo-planar binomials in characteristic two and related schemes

Fu H.L., Lin Y.H., Mishima M.: Optimal conflict-avoiding codes of even length and weight 3. IEEE Trans. Inf. Theory 56(11), 5747–5756 (2010).

Fu H.L., Lo Y.H., Shum K.W.: Optimal conflict-avoiding codes of odd length and weight three. Des. Codes Cryptogr. 1–21 (2012). doi:10.1007/s10623-012-9764-5.

Györfi L., Vajda I.: Constructions of protocol sequences for multiple access collision channel without feedback. IEEE Trans. Inf. Theory 39(5), 1762–1765 (1993).

Jimbo M., Mishima M., Janiszewski S., Teymorian A.Y., Tonchev V.: On conflict-avoiding codes of length \(n=4m\) for three active users. IEEE Trans. Inf. Theory 53(8), 2732–2742 (2007).

Levenshtein V.I.: Conflict-avoiding codes and cyclic triple systems. Probl. Inf. Transm. 43(3), 199–212 (2007).

Levenshtein V.I., Tonchev V.D.: Optimal conflict-avoiding codes for three active users. In: Proceedings of IEEE Internation Symposium on Information Theory, Adelaide, Australia. pp. 535–537. (2005).

Lin Y., Mishima M., Satoh J., Jimbo M.: Optimal equi-difference conflict-avoiding codes of odd length and weight three. Finite Fields Appl. 26, 49–68 (2014).

Ma W., Zhao C., Shen D.: New optimal constructions of conflict-avoiding codes of odd length and weight 3. Des. Codes Cryptogr. 1–14 (2013). doi:10.1007/s10623-013-9827-2.

Mishima M., Fu H.L., Uruno S.: Optimal conflict-avoiding codes of length \(n\equiv 0\) (mod 16) and weight 3. Des. Codes Cryptogr. 52(3), 275–291 (2009).

10.

Momihara K.: Necessary and sufficient conditions for tight equi-difference conflict-avoiding codes of weight three. Des. Codes Cryptogr. 45(3), 379–390 (2007).

11.

Momihara K., Müller M., Satoh J., Jimbo M.: Constant weight conflict-avoiding codes. SIAM J. Discret. Math. 21(4), 959–979 (2007).

12.

The OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences. http://oeis.org.

13.

Shum K.W., Wong W.S., Chen C.S.: A general upper bound on the size of constant-weight conflict-avoiding codes. IEEE Trans. Inf. Theory 56(7), 3265–3276 (2010).

14.

Shum K.W., Wong W.S.: A tight asymptotic bound on the size of constant-weight conflict-avoiding codes. Des. Codes Cryptogr. 57(1), 1–14 (2010).

15.

Wu S.L., Fu H.L.: Optimal tight equi-difference conflict-avoiding codes of length \(n=2^k\pm 1\) and weight 3. J. Comb. Des. 21(6), 223–231 (2013).

Titel: Weighted maximum matchings and optimal equi-difference conflict-avoiding codes
verfasst von: Yuan-Hsun Lo
Hung-Lin Fu
Yi-Hean Lin
Publikationsdatum: 01.08.2015
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 2/2015
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-014-9961-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 2/2015

MJH: a faster alternative to MDC-2

Search problems in vector spaces

A new iterative computer search algorithm for good quasi-twisted codes

Two constructions of balanced Boolean functions with optimal algebraic immunity, high nonlinearity and good behavior against fast algebraic attacks

New pseudo-planar binomials in characteristic two and related schemes

Monomial isomorphisms of cyclic codes