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

DOI10.1007/S10623-017-0428-3zbMATH Open1411.11035arXiv2010.05415OpenAlexW3102065527MaRDI QIDQ1650802FDOQ1650802

Authors: Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan 

Publication date: 13 July 2018

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

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.

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

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

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)

Cites Work

• An Efficient Algorithm for Generating Necklaces with Fixed Density
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multiplicative number theory. I. Classical theory
• Title not available (Why is that?)
• Counting permutations with given cycle structure and descent set
• Restricted linear congruences
• On an Almost-Universal Hash Function Family with Applications to Authentication and Secrecy Codes
• Cyclic permutations realized by signed shifts
• Counting surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group with motivations from string theory and QFT
• Symmetry types of periodic sequences
• On the number of distinguished representations of a group element
• The cycle enumerator of unimodal permutations
• Title not available (Why is that?)
• On Varshamov-Tenengol'ts codes and a conjecture of L. A. Bassalygo
• Title not available (Why is that?)
• A class of codes for asymmetric channels and a problem from the additive theory of numbers
• Arithmetic-progression-weighted subsequence sums
• Distinct solution to a linear congruence
• Title not available (Why is that?)
• The arithmetic Tutte polynomials of the classical root systems
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

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
• Title not available (Why is that?)
• 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)