scientific article; zbMATH DE number 1498827

MaRDI QIDQ4501018zbMATH OpenFDO

Authors V. Yu. Solomennikov, Yu. L. Sagalovich

Publication date 3 September 2000

zbMATH Keywords

hash distancelinear hash codes

Mathematics Subject Classification ID

Bounds on codes (94B65)

Review text

Let \(C\) be a block code over \(\text{GF}(q)\) with \(|C|\geq t\geq 2\). The \(t\)-th hash distance of \(C\) was introduced by \textit{L.~A.~Bassalygo, M.~Burmester, A.~Dyachkov}, and \textit{G.~Kabatianski} in [Proc. IEEE Int. Symp. on Information Theory, Ulm, Germany (1997)] as the maximal number \(d_t=d_t(C)\) such that any \(t\) distinct codewords are pairwise different at least in \(d_t\) positions. The distance \(d_2(C)\) equals the minimum Hamming distance of \(C\). A code \(C\) is called a hash code of depth \(t\) if \(d_t(C)>0\) (it is easy to see that \(d_t(C)=0\) whenever \(t>q\)). The hash distance of some known codes (the dual Hamming codes, MDS codes, 1-extended Reed--Solomon code) is estimated. Conditions for existence of linear hash codes are presented. An asymptotic upper bound on the rate of a linear hash code is obtained. For the entire collection see [Zbl 0918.00043].

Recommendations

• On linear hash codes
• Provably Good Codes for Hash Function Design
• Beating Fredman-Komlós for perfect \(k\)-hashing
• Estimates for distribution of the minimal distance of a random linear code

Cited in

(5)

• On linear hash codes
• Generalized hashing and parent-identifying codes.
• Beating Fredman-Komlós for perfect \(k\)-hashing
• Beating Fredman-Komlós for Perfect k-Hashing.
• Hash property and coding theorems for sparse matrices and maximum-likelihood coding

This page was built for publication:

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