nach oben

Designs, Codes and Cryptography

Erschienen in:

19.10.2017

Unweighted linear congruences with distinct coordinates and the Varshamov–Tenengolts codes

verfasst von: Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan

Erschienen in: Designs, Codes and Cryptography | Ausgabe 9/2018

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

In this paper, we first give explicit formulas for the number of solutions of unweighted linear congruences with distinct coordinates. Our main tools are properties of Ramanujan sums and of the discrete Fourier transform of arithmetic functions. Then, as an application, we derive an explicit formula for the number of codewords in the Varshamov–Tenengolts code \(VT_b(n)\) with Hamming weight k, that is, with exactly k 1’s. The Varshamov–Tenengolts codes are an important class of codes that are capable of correcting asymmetric errors on a Z-channel. As another application, we derive Ginzburg’s formula for the number of codewords in \(VT_b(n)\), that is, \(|VT_b(n)|\). We even go further and discuss connections to several other combinatorial problems, some of which have appeared in seemingly unrelated contexts. This provides a general framework and gives new insight into all these problems which might lead to further work.

Nächster Artikel Hadamard full propelinear codes of type Q; rank and kernel

Adams D., Ponomarenko V.: Distinct solution to a linear congruence. Involve 3, 341–344 (2010).MathSciNetCrossRefMATH

Archer K., Elizalde S.: Cyclic permutations realized by signed shifts. J. Comb. 5, 1–30 (2014).MathSciNetMATH

Ardila F., Castillo F., Henley M.: The arithmetic Tutte polynomials of the classical root systems. Int. Math. Res. Not. 2015, 3830–3877 (2015).MathSciNetMATH

Bibak K., Kapron B.M., Srinivasan V.: Counting surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group with motivations from string theory and QFT. Nucl. Phys. B 910, 712–723 (2016).MathSciNetCrossRefMATH

Bibak K., Kapron B.M., Srinivasan V.: A generalization of Schönemann’s theorem via a graph theoretic method (submitted).

Bibak K., Kapron B.M., Srinivasan V., Tauraso R., Tóth L.: Restricted linear congruences. J. Number Theory 171, 128–144 (2017).MathSciNetCrossRefMATH

Bibak K., Kapron B.M., Srinivasan V., Tóth L.: On an almost-universal hash function family with applications to authentication and secrecy codes, Int. J. Found. Comput. Sci. (to appear).

Brauer A.: Lösung der Aufgabe 30. Jber. Deutsch. Math.–Verein 35, 92–94 (1926).

Dolecek L., Anantharam V.: Repetition error correcting sets: explicit constructions and prefixing methods. SIAM J. Discret. Math. 23, 2120–2146 (2010).MathSciNetCrossRefMATH

10.

Gessel I.M., Reutenauer C.: Counting permutations with given cycle structure and descent set. J. Comb. Theory Ser. A 64, 189–215 (1993).MathSciNetCrossRefMATH

11.

Gevorkyan D.M., Kabatiansky G.A.: On Varshamov–Tenengolts codes and a conjecture of L.A. Bassalygo. Probl. Inf. Transm. 28, 393–395 (1992).MathSciNet

12.

Gilbert E.N., Riordan J.: Symmetry types of periodic sequences. Illinois J. Math. 5, 657–665 (1961).MathSciNetMATH

13.

Ginzburg B.D.: A certain number-theoretic function which has an application in coding theory (Russian). Problemy Kibernet. 19, 249–252 (1967).MathSciNetMATH

14.

Grynkiewicz D.J., Philipp A., Ponomarenko V.: Arithmetic-progression-weighted subsequence sums. Israel J. Math. 193, 359–398 (2013).MathSciNetCrossRefMATH

15.

Gupta H.: Partitions–a survey. J. Res. Nat. Bur. Stand. B. Math. Sci. 74B, 1–29 (1970).MathSciNetCrossRefMATH

16.

Jacobson D., Williams K.S.: On the number of distinguished representations of a group element. Duke Math. J. 39, 521–527 (1972).MathSciNetCrossRefMATH

17.

Kluyver J.C.: Some formulae concerning the integers less than \(n\) and prime to \(n\). Proc. R. Neth. Acad. Arts Sci. (KNAW) 9, 408–414 (1906).

18.

Lehmer D.N.: Certain theorems in the theory of quadratic residues. Am. Math. Mon. 20, 151–157 (1913).MathSciNetCrossRef

19.

Levenshtein V.I.: Binary codes capable of correcting deletions, insertions and reversals (in Russian). Doklady Akademii Nauk SSSR 163, 845–848 (1965). English translation in Soviet Physics Dokl. 10, 707–710 (1966).

20.

Levenshtein V.I.: Binary codes capable of correcting spurious insertions and deletions of ones (in Russian). Problemy Peredachi Informatsii 1, 12–25 (1965). English translation in Problems of Information Transmission 1, 8–17 (1965).

21.

Maze G.: Partitions modulo \(n\) and circulant matrices. Discret. Math. 287, 77–84 (2004).MathSciNetCrossRefMATH

22.

Milnor J., Thurston W.: On iterated maps of the interval, dynamical systems. Lecture Notes in Mathematics, Vol. 1342, pp. 465–563. Springer, Berlin (1988)

23.

Montgomery H.L., Vaughan R.C.: Multiplicative Number Theory I: Classical Theory. Cambridge University Press, Cambridge (2006).CrossRefMATH

24.

Rademacher H.: Aufgabe 30. Jber. Deutsch. Math.–Verein 34, 158 (1925).

25.

Razen R., Seberry J., Wehrhahn K.: Ordered partitions and codes generated by circulant matrices. J. Comb. Theory Ser. A 27, 333–341 (1979).MathSciNetCrossRefMATH

26.

Ruskey F., Sawada J.: An efficient algorithm for generating necklaces with fixed density. SIAM J. Comput. 29, 671–684 (1999).MathSciNetCrossRefMATH

27.

Schönemann T.: Theorie der symmetrischen Functionen der Wurzeln einer Gleichung. Allgemeine Sätze über Congruenzen nebst einigen Anwendungen derselben. J. Reine Angew. Math. 1839, 231–243 (1839).CrossRef

28.

Sloane N.J.A.: On single-deletion-correcting codes. In: Arasu K.T., Seress A. (eds.) Codes and Designs, Ohio State University, May 2000 (Ray-Chaudhuri Festschrift), pp. 273–291. Walter de Gruyter, Berlin (2002).

29.

Stanley R.P.: Enumerative Combinatorics, vol. 1, 2nd edn. Cambridge University Press, Cambridge (2012).MATH

30.

Stanley R.P., Yoder M.F.: A study of Varshamov codes for asymmetric channels, Jet Propulsion Laboratory, Technical Report 32-1526, Vol. XIV, pp. 117–123 (1973).

31.

Thibon J.-Y.: The cycle enumerator of unimodal permutations. Ann. Comb. 5, 493–500 (2001).MathSciNetCrossRefMATH

32.

Varshamov R.R.: On an arithmetic function with an application in the theory of coding (in Russian). Dokl. Akad. Nauk SSSR 161, 540–543 (1965).MathSciNet

33.

Varshamov R.R.: A class of codes for asymmetric channels and a problem from the additive theory of numbers. IEEE Trans. Inf. Theory 19, 92–95 (1973).MathSciNetCrossRefMATH

34.

Varshamov R.R., Tenengolts G.M.: Codes which correct single asymmetric errors (in Russian), Avtomatika i Telemekhanika 26, 288–292 (1965). English translation in Automation and Remote Control 26, 286–290 (1965).

35.

von Sterneck R.D.: Ein Analogon zur additiven Zahlentheorie, Sitzber, Akad. Wiss. Wien, Math. Naturw. Klasse 111 (Abt. IIa), 1567–1601 (1902).

36.

Weiss A., Rogers T.D.: The number of orientation-reversing cycles in the quadratic map. CMS Conference Proceedings on Oscillation, Bifurcation and Chaos 8, 703–711 (1987).

Titel: Unweighted linear congruences with distinct coordinates and the Varshamov–Tenengolts codes
verfasst von: Khodakhast Bibak
Bruce M. Kapron
Venkatesh Srinivasan
Publikationsdatum: 19.10.2017
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 9/2018
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-017-0428-3

Springer Professional

Abstract

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

Weitere Artikel der Ausgabe 9/2018

On the number of inequivalent Gabidulin codes

Fourier transforms and bent functions on finite groups

Improved cryptanalysis of rank metric schemes based on Gabidulin codes

On group codes with complementary duals

On critical exponents of Dowling matroids

Flags of almost affine codes and the two-party wire-tap channel of type II