Almost affine codes are generalization for widely used linear codes which can be used in ideal perfect secret sharing schemes. In [1] Simonis and Ashikhmin defined and studied some properties of almost affine codes. In the other hand quasi-uniform codes [2] are generalization of almost affine codes. In this paper we show that duality of chains of linear codes holds in the almost affine case as well and we make a conjecture about such property for quasi-uniformcodes.
almost affine codes, quasi-uniform codes, matroids
Introduction
Linear block codes play a key role in the theory of error correction. A 
-ary linear code of length 
is a 
-dimensional vector subspace of 
where 
is a finite field with elements, also known as the alphabet of the code. One of the reasons why linear codes dominate the industry is that linear code can be described completely with its generator matrix. Because of the convenience, linear codes possess some restrictions, and it can be shown [9] that linear codes are not sufficient to achieve the maximal capacity for information flow in a multi-source network.
In [1] Simonis and Ashikhmin proposed another class of error correcting codes, namely almost affine codes. The initial motivation for authors was studying the ideal perfect secret sharing schemas. Basically, almost affine codes are generalization for linear codes with less restrictions. However, its turs out that almost affine codes share some properties with linear codes, like the subject of this paper – duality of chains of codes. Or specifically the demi-matroids associated with such chains.
The other step towards to generalization in error correction is quasi-uniform codes [3]. It can be shown that for small length (
) almost affine codes are linear and, therefore satisfy the Ingleton inequality. But there is exists a quasi-uniform code of length equal to 4 which violates the Ingleton inequality.
We continue with giving formal definitions of concepts discussed earlier, starting with almost affine codes.
Definition 1. Let 
be a finite set of cardinality . A code 
is called almost affine if it satisfies the following condition for any subset 
As we can see from the definition above does not have to be a field. And the condition says that projection to any subset of 
has an integer dimension. It is easy to verify that any linear code 
satisfies this condition, therefore is an almost affine code and 
is called rank function of the code.
The main tool to study linear codes is their matrix representation. For almost affine codes we do not have such tool. But we have generalization of matrices – matroids. There are at least four equivalent definitions of matroids, we proceed with the definition via rank function.
Definition 2. Let 
be a finite set called ground set, and be a function 
. Then matroid 
is a pair 
if satisfies the following axioms for any 
and any 
(
) 
,
(
) 
,
(
) If 
, then 
It can be shown that the function from definition 1 satisfies the axioms above, and an almost affine code induces a matroid. If from definition above satisfies only ( ) and ( ) axioms, then a pair 
is a demi-matroid. We continue with the core theorem of the article.
Theorem 1. Let 
be a chain of almost affine codes with respective rank functions 
. Then 
with 
is a demi-matroid.
The prove of this theorem can be found in [6].
Demi-matroids have two types of duality. The dual demi-matroid to a given demi-matroid 
is 
, where 
. The supplement dual demi-matroid to a given one is 
, where 
. It is known fact due to [10], that , 
and combination of the two types 
are demi-matroids.
Chains of almost affine codes
In this section we show that for any chain of almost affine codes and rank functions pairs 
, 
and 
are also demi-matroids with
To do so we look at these three functions individually and show that under some circumstances they are equal to 
, 
, 
or just 
.
Lemma 1. Let be a chain of almost affine codes with respective rank functions and 
and 
. Then 
if 
is odd and 
if is even.
Proof. For any 
we need to show
The equalities hold with 
. Assume (*) holds for any 
, prove the induction step and show that 
and 
By assumption we have 
, notice that 
by definition. Then 
, so by the definition of the dual we have:
Now we look at 
, combining with the above we have 
, so by the definition of the supplement dual we have:
Thus, lemma is proven by induction.
Lemma 2. Let be a chain of almost affine codes with respective rank functions and 
and 
, then 
.
Proof.
Before the last lemma we need the fact that 
we have 
. Indeed, by definition, we have
At the same time, we have
Lemma 3. Let be a chain of almost affine codes with respective rank functions and and 
. Then 
if is even and 
if is odd.
Proof. The proof is similar to the proof of lemma 1.
These three lemmas lead us to the following theorem.
Theorem 2. Let be a chain of almost affine codes with respective rank functions , then the pairs 
, 
and 
are demi-matroids.
Proof. By the theorem 1, 
is a demi-matroid, 
, 
and 
are demi-matroids as well. And by the previous lemmas we showed that the pairs , and are equal to 
, 
, 
or 
depending on the parity of . Hence, the theorem is proven.
The theorem above is also proven in the article [6], but this prove is different. Applications of duality of chains of almost affine codes can be found in [6], [7] and [10].
Quasi-uniform codes
For proper introduction to quasi-uniform codes one can look at the article [3], where authors introduced these codes via random variable vectors. The simple recap is that quasi-uniform code 
induces a random variable vector which is distributed uniformly over projection to any . This class of codes does not have rank function which can be used to construct its matroid. But quasi-uniform codes induce a polymatroids instead.
Definition 3. For a finite set and 
be a real value function 
, then the pair 
is a polymatroid if for any 
satisfies the following axioms:
( ) 
,
( ) 
,
( ) 
If satisfies cardinality bound 
and 
is a non-negative integer, then is a matroid. If from definition above satisfies only ( ) and ( ) axioms, then a pair is a demi-polymatroid.
Any given quasi-uniform code 
induces a polymatroid by defining 
, where 
is the entropy function of the codeword random variable. We conjecture that the chain duality discussed in the previous section holds for chains of quasi-uniform codes with respective demi-polymatroids. Recently it was shown in [8] that similar chain duality holds for rank-metric codes with 
-demi-polymatroids which are the special case of demi-polymatroids. However, the general case is still open.
1. Simonis J. and A. Ashikhmin, “Almost Affine Codes.” Designs, Code and Cryptography, pp. 179-197, (1998).
2. Chan, H. and R. Yeung. “A combinatorial approach to information inequalities.” Infor-mation Theory and Networking Workshop (Cat. No.99EX371) (1999): 63-.
3. Chan, T., A. Grant and T. Britz. “Quasi-Uniform Codes and Their Applications.” IEEE Transactions on Information Theory 59 (2013): 7915-7926.
4. Oxley, J.. “Matroid Theory (Oxford Graduate Texts in Mathematics).” (2006).
5. Lin, Shu and D. Costello. “Error control coding - fundamentals and applications.” Prentice Hall computer applications in electrical engineering series (1983).
6. Johnsen, T. and Hugues Verdure. “Flags of almost affine codes.” ArXiv abs/1704.02819 (2017): n. pag.
7. Johnsen, T. and Hugues Verdure. “Generalized Hamming Weights for Almost Affine Codes.” IEEE Transactions on Information Theory 63 (2017): 1941-1953.
8. Ghorpade, S. and T. Johnsen. “A Polymatroid Approach to Generalized Weights of Rank Metric Codes.” Des. Codes Cryptogr. 88 (2020): 2531-2546.
9. Chan, T. and A. Grant. “Dualities Between Entropy Functions and Network Codes.” IEEE Transactions on Information Theory 54 (2008): 4470-4487.
10. Britz, T., T. Johnsen, D. Mayhew and K. Shiromoto. “Wei-type duality theorems for matroids.” Designs, Codes and Cryptography 62 (2012): 331-341.
