Antichain codes
type: Item
instance of: scholarly article
title: Antichain codes
zbMATH Open document ID: 0961.94017
DOI: 10.1023/A:1008329017752
author: Gérard Cohen
author: Sylvia Encheva
author: Gilles Zémor
published in: Designs, Codes and Cryptography
publication date: 2001-01-01T00:00:00Z
review text: A binary vector \(x\) is identified with its support, the set of its non-zero coordinate positions. The authors consider binary linear codes \(C[n,k,d]\) with weight hierarchy \(\{d_1=d,\dots,d_k=n\}\), where \(d_i\) is the minimum support size of a \(i\)-th dimensional subcode of \(C\). In the wire-tap channel [\textit{L. H. Ozarow} and \textit{A. D. Wyner}, AT\&T Bell Lab. Tech. J. 63, 2135-2157 (1984; Zbl 0587.94013)], the dual of \(C\) is used in a coset-coding scheme: the interception by an enemy of \(d_i\) well chosen binary digits leaks \(i\) information bits about the system. If \(C\) satisfies the chain condition [\textit{S. Encheva} and \textit{T. Kløve}, IEEE Trans. Inf. Theory 40, 175-180 (1994; Zbl 0811.94035)], i.e. there exists a chain of nested \(C_i\)'s, then the enemy gets the next \(i\)-th bit by intercepting \(d_i-d_{i-1}\) digits. In particular second bit requires \(d_2-d\) digits. The authors want to maximize the enemy's effort to get this second bit. To that end, they define \(g_2=\min |c_1\cup c_2|\), \(|c_1|=d\), where \(c_1, c_2\) are two distinct codewords. The authors search for codes with \(g_2\gg d_2\), which insures that \(g_2-d\gg d_2-d\) digits need to be intercepted before obtaining the second bit of information. In the present paper it is shown that almost all codes satisfy this antichain condition, i.e. the minimum length of a two-dimensional subcode of a code \(C\) increases if the subcode is constrained to contain a minimum weight codeword. In particular, almost no code satisfies the chain condition. Another possible application is to list decoding for the erasure channel. In passing, the authors study the typical behaviour of codes with respect to generalized distances and show that almost all lie on a generalized Varshamov-Gilbert bound.
Mathematics Subject Classification ID: 94B60
Mathematics Subject Classification ID: 94B65
zbMATH DE Number: 1548357
MaRDI profile type: Publication
Recommended article: Minimum support weights of binary codes
Recommended article: Generalized Hamming weights of linear codes
Recommended article: Generalizations of the Griesmer bound
Recommended article: The linear programming bound for binary linear codes
Recommended article: Codes satisfying the chain condition
Recommended article: A geometric characterization of minimal codes and their asymptotic performance
Recommended article: Q4502620
Recommended article: An updated table of minimum-distance bounds for binary linear codes
Recommended article: Value functions and two classes of binary codes
Recommended article: On the Second Greedy Weight for Linear Codes of Dimension at Least&gt;tex&lt;$4$&gt;/tex&lt;
description: scientific article; zbMATH DE number 1548357