Antichain codes
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.
- Minimum support weights of binary codes
- Generalized Hamming weights of linear codes
- Generalizations of the Griesmer bound
- The linear programming bound for binary linear codes
- Codes satisfying the chain condition
- A geometric characterization of minimal codes and their asymptotic performance
- scientific article; zbMATH DE number 1504658
- An updated table of minimum-distance bounds for binary linear codes
- Value functions and two classes of binary codes
- On the Second Greedy Weight for Linear Codes of Dimension at Least>tex<$4$>/tex<
- On self-dual ternary codes and their coordinate ordering.
- Flags of almost affine codes and the two-party wire-TAP channel of type II
- Further results on the second relative greedy weight of 3-dimensional codes
- Greedy weights for matroids
- The fullrank value function
- On the second relative greedy weight
- Antichain Simplices
This page was built for publication: Antichain codes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1591641)
