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

DOI10.1007/S10623-017-0428-3MaRDI QIDQ1650802zbMATH OpenOpenAlexFDO

Authors Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan

Publication date 13 July 2018

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.05415

zbMATH Keywords

discrete Fourier transformlinear congruenceHamming weightRamanujan sum\(Z\)-channeldistinct coordinatesVarshamov-Tenengolts code

Mathematics Subject Classification ID

Cryptography (94A60) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Congruences in many variables (11D79) Partitions; congruences and congruential restrictions (11P83) Fourier coefficients, Fourier series of functions with special properties, special Fourier series (42A16)

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 $V{T}_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 $V{T}_b(n)$, that is, $|V{T}_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.

Recommendations

• Exact and Approximate Expressions for the Probability of Undetected Errors of Varshamov–Tenengol'ts Codes
• On Varshamov-Tenengol'ts codes and a conjecture of L. A. Bassalygo
• The structure of linear codes of constant weight
• An explicit formula for a weight enumerator of linear-congruence codes
• On the Weight Distributions of Cosets of a Linear Code

Cites work

• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 4064114 (Why is no real title available?)
• scientific article; zbMATH DE number 4086578 (Why is no real title available?)
• scientific article; zbMATH DE number 1867238 (Why is no real title available?)
• scientific article; zbMATH DE number 3228267 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• scientific article; zbMATH DE number 3301965 (Why is no real title available?)
• scientific article; zbMATH DE number 3414190 (Why is no real title available?)
• A class of codes for asymmetric channels and a problem from the additive theory of numbers
• An Efficient Algorithm for Generating Necklaces with Fixed Density
• Arithmetic-progression-weighted subsequence sums
• Counting permutations with given cycle structure and descent set
• Counting surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group with motivations from string theory and QFT
• Cyclic permutations realized by signed shifts
• Distinct solution to a linear congruence
• Multiplicative number theory. I. Classical theory
• On Varshamov-Tenengol'ts codes and a conjecture of L. A. Bassalygo
• On an Almost-Universal Hash Function Family with Applications to Authentication and Secrecy Codes
• On the number of distinguished representations of a group element
• Ordered partitions and codes generated by circulant matrices
• Partitions - a survey
• Partitions modulo \(n\) and circulant matrices
• Repetition error correcting sets: explicit constructions and prefixing methods
• Restricted linear congruences
• Symmetry types of periodic sequences
• The arithmetic Tutte polynomials of the classical root systems
• The cycle enumerator of unimodal permutations

Cited in

(7)

• Distinct coordinate solutions of linear equations over finite fields
• The Modular Subset-Sum Problem and the size of deletion correcting codes
• Deletion correcting codes meet the Littlewood-Offord problem
• scientific article; zbMATH DE number 3856983 (Why is no real title available?)
• Extensions of Schönemann's theorem in Galois rings
• A generalization of Schönemann's theorem via a graph theoretic method
• Order-restricted linear congruences

This page was built for publication: Unweighted linear congruences with distinct coordinates and the Varshamov-Tenengolts codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1650802)