Antichain codes (Q1591641)

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.