Linear-Function Correcting Codes
Rohit Premlal B. Sundar Rajan

 






Linear-Function Correcting Codes
    Rohit Premlal        and B. Sundar Rajan

	Department of Electrical Communication Engineering, Indian Institute of Science, Bengaluru, India 

		Email: {rohitpl, bsrajan}@iisc.ac.in

    April 29, 2024
==========================================================================================================================================================================================







 In this paper, we study linear-function correcting codes,
a class of codes designed to protect linear function evaluations
of a message against errors. The work "Function-Correcting Codes" by Lenz et al. 2023 provides a graphical representation for the problem of constructing function-correcting codes. We use this graph to get a lower bound the on redundancy required for function correction. By considering the function to be a bijection, such an approach also provides a lower bound on the redundancy required for classical systematic error correcting codes. For linear-function correction, we characterise the spectrum of the adjacency matrix of this graph, which gives rise to lower bounds on redundancy. The work "Function-Correcting Codes" gives an equivalence between function-correcting codes and irregular-distance codes. We identify a structure imposed by linearity on the distance requirement of the equivalent irregular-distance code which provides a simplified Plotkin-like bound. We propose a version of the sphere packing bound for linear-function correcting codes.  We identify a class of linear functions for which an upper bound proposed by Lenz et al., is tight. We also identify a class of functions for which coset-wise coding is equivalent to a lower dimensional classical error correction problem.




§ INTRODUCTION


In a typical communication system, the sender wishes to transmit a message to the receiver through an erroneous channel. All symbols of the message are considered equally important and the objective is to create an error correcting code (ECC) with a decoder that can recover the entire message accurately. However, in certain scenarios, the receiver may only be interested in a specific function of the message. In such cases, if the sender knows the function, the message can be encoded so as to ensure that the desired attribute is protected against errors. This approach gives rise to a new class of codes known as function-correcting codes (FCCs) as introduced in <cit.>.

The paradigm of FCCs was introduced in <cit.>, which considers systematic codes that protect a general function evaluation of the message from errors. The channel considered is the substitution channel, in which the errors are symbol substitutions on the transmitted vector. They proposed a function-dependent graph for the problem of constructing FCCs. The vertex set of the graph represents possible codewords of the FCC and two
vertices are connected if and only if they can be contained together in an FCC. Thus, independent sets of the graph of sufficient cardinality form FCCs. It is difficult to characterise the independent sets of this graph for a general function. An equivalence between FCCs and irregular-distance codes is shown in <cit.>, where the distance requirements of the irregular-distance code is dictated by the function of interest. Since the problem heavily depends on the function, simplified sub optimal bounds on redundancy were proposed that are easier to evaluate. A fundamental result from classical coding theory is the Singleton bound, which says that to correct t errors, at least 2t redundant symbols have to be added. It is shown in <cit.> that this lower bound on redundancy holds for FCCs as well. It is also known that there are no non-trivial binary classical ECCs that achieve this lower bound. But in the case of FCCs, a class of functions called locally-binary functions have been proposed for which there exists encoding and decoding schemes so that t errors can be corrected using 2t redundant symbols, for a particular range of t. They also compare schemes for certain functions with the corresponding classical ECCs and show that function correction can be done with a lower redundancy length than what is required for classical error correction. FCCs for symbol-pair read channels were explored in <cit.>. Bounds on the optimal redundancy is provided and a counterpart of locally binary functions is proposed - pair-locally binary functions.

An application that motivates the use of systematic FCCs is archival data storage. Consider a message stored in a noisy storage medium after being encoded using an ECC. Say an attribute of the stored data is to be stored in the medium with an even higher error correcting capability. The classical approach is to use an ECC of higher capability. But in <cit.>, it is proposed to store the parity obtained by using a systematic FCC.




 §.§ Contributions and Organisation

In this work, we study FCCs for the case when    the function evaluated is linear. We show that the bounds provided in <cit.> can be simplified using the structure imposed by linearity. We also propose additional bounds on the redundancy and propose classes of functions where FCCs can achieve lower redundancy lengths than classical codes. The technical contributions of this paper are summarised:

	
  * A graph based representation of the problem is proposed in <cit.>. Independent sets of this graph, of sufficient cardinality can be chosen to be an FCC. An upper bound for the independence number of this graph is proposed which leads to lower bounds on the redundancy of the FCC. We consider a different graph with the same vertex set as the original one but with a maximum independent set which is a superset of that of the original graph. We express this graph as the Cartesian product of two smaller graphs which helps in characterising its independence number (Section 
	<ref>: Theorem <ref>).
	
	
  * In <cit.>, a Plotkin-like bound is derived for FCCs. The Hamming distance distribution of the message vector space is required for computing this bound. For linear functions it is shown that only the weight distribution of the kernel of the function is needed to compute the bound (Section 
	<ref>: Corollary <ref>).
	
	
  * A characterization of the graphical representation of FCCs is given for linear functions. We show that its adjacency matrix has a symmetric block circulant structure. (Section <ref>: Theorem <ref>).
	
	
  * Using this structure, we show that for linear functions, the
	adjacency matrix is diagonalised by the tensor powers of
	DFT matrices. As a special case, for linear functions whose
	domain is a vector space over a field of characteristic
	2, we show that Hadamard matrices can diagonalise the
	adjacency matrix. The obtained spectrum of the graph
	is used to obtain bounds on redundancy.(Section III-B:
	Corollary 5). (Section <ref>: Corollary <ref>).
	
	
  * Coset-wise coding is proposed where all the messages evaluated to the same function value are assigned the same parity. A sphere packing based bound is proposed for such coding schemes (Section <ref>: Theorem <ref>).
	
	
  * A class of linear functions for which coset-wise coding is optimal is identified and a scheme for encoding such functions is provided. (Section <ref> ).
	

	
  * A class of linear functions is identified for which the problem of coset-wise coding is equivalent to a lower dimensional classical error correction problem (Section <ref>).






 §.§ Notations

The set of all positive integers less than or equal to N is denoted by [N]. The set of all positive integers is denoted by ℕ and the set of all non-negative integers is denoted by ℕ_0. The set of all complex numbers is denoted by ℂ. The set of all real numbers is denoted by ℝ. A finite field of size q is represented as 𝔽_q. A vector, 𝐚∈𝔽_q^n is represented as (a_1a_2 a
	_n).	The Hamming weight of 𝐚∈𝔽_q^n is denoted by w_H(𝐚). For k≤ l≤ n, 𝐚[k:l] represents the vector (a_ka_k+1 a_l).
	For any set of vectors X ⊆𝔽_q^n, w_H(X) denotes the Hamming weight of the minimum Hamming weight vector in X. For any pair of vectors 𝐱,𝐲∈𝔽_q^n, d_H(𝐱,𝐲) denotes the Hamming distance between 𝐱 and 𝐲. For an N× N matrix 𝐃, [𝐃]_ij denotes the (i,j)th entry of 𝐃 and 𝐃_(i) denotes the ith column of 𝐃. For sets of positive integers X ,Y⊆ [N], 𝐃_X,Y denotes the submatrix of 𝐃 whose rows are indexed by X and columns by Y. We use 𝐞_i∈𝔽_q^n to represent the unit vector with a 1 in the ith coordinate and 0s everywhere else. We use 𝐈_n to denote the identity matrix of order n. For a matrix 𝐗∈ℂ^n× n, 𝐗^† denotes its conjugate transpose. For matrices 𝐗 and 𝐘, 𝐗⊗𝐘 denotes the Tensor product of 𝐗 and 𝐘. We use 𝐗^⊗ n to denote the nth order tensor power of 𝐗 i.e., 𝐗^⊗ n = ⊗_i=1^n𝐗. The set of all vectors that are at a Hamming distance less than or equal to t from 𝐮∈𝔽_q
^n is denoted by B_H(𝐮,t).
For any x∈ℝ, [x]^+ max(x,0). For any two integers a and n,

    <a>_n 
    		
    		a(modn);   if  a(modn) 0 
    
    		n;    otherwise.





§ PRELIMINARIES





 §.§ Graphs


	A graph 𝒢 is a pair (V,E) where V is the vertex set and E⊆V×V is the edge set. We say that vertices v_1 and v_2 are connected if (v_1,v_2)∈ E. In this paper we consider simple graphs, i.e., there are no loops or multiple edges. 
	
	An independent set of 𝒢 is a set S⊆V such that v_1,v_2∈S (v_1,v_2) ∉E.
The independence number α is the cardinality of the maximum independent set. A maximum independent set of 𝒢 is called an α-set of 𝒢. 

The Cartesian product 𝒢ℋ of two graphs 𝒢 = (V,E ) and ℋ = (V',E') is a graph with its vertex set given by V×V' and two vertices (u,v) and (u',v') are connected in 𝒢ℋ iff 

	
  * u=u' and (v,v')∈E' or,
	
	
  * (u,u') ∈E and v=v'.




 §.§ Circulant Matrices

An n× n matrix 𝐀 is said to be a circulant matrix if [𝐀]_ij =[𝐀]_<i+1>_n<j+1>_n for all  i,j∈[n]. An nm× nm matrix 𝐁 is said to be a block circulant matrix if it is of the following block matrix form:


    𝐁 = [ 𝐁_11 𝐁_12 𝐁_13      𝐁_1n; 𝐁_21 𝐁_22 𝐁_23      𝐁_2n;    ⋮    ⋮    ⋮    ⋱    ⋮; 𝐁_n1 𝐁_n2 𝐁_n3      𝐁_nn ],
where each 𝐁_ij is an m× m matrix and 𝐁_ij=𝐁__<i+1>_n<j+1>_n
for all i,j∈[n].

It is known that an n× n circulant matrix is diagonalized by the nth order Discrete Fourier Transform (DFT) matrix given by 

    𝐖_n=[            1            1            1            1                         1;            1            ω          ω^2          ω^3                     ω^n-1;            1          ω^2          ω^4          ω^8                  ω^2(n-1);            ⋮            ⋮            ⋮            ⋱            ⋮;            1        ω^n-1     ω^2(n-1)     ω^3(n-1)              ω^(n-1)(n-1);              ],

where ω is the nth root of unity.




 §.§ Hadamard Matrices


A Hadamard matrix of order n is a real n× n matrix 𝐇_n taking values from the set {1,-1} such that 𝐇_n^T𝐇_n = n𝐈_n. The Sylvester construction <cit.> gives Hadamard matrices when n is a power of 2 as follows:

    𝐇_1 = [  1  1;  1 -1 ] and 𝐇_n = [  𝐇_n-1  𝐇_n-1;  𝐇_n-1 -𝐇_n-1 ].

Note that 𝐇_2 is equal to the DFT matrix of order 2, 𝐖_2.




 §.§ Classical Error Correcting Codes


	An (n,M,d)_q code 𝒞 is a set of M vectors of length n with elements from some finite set (alphabet) of cardinality q (say 𝔽_q), such that d is the minimum Hamming distance between any pair of vectors (codewords) in 𝒞. A code of alphabet size q is said to be a q-ary code. 
	
	A code of minimum distance d can correct any error of length d-1/2.
	
	The maximum number of codewords in any q-ary code of length n and minimum distance d between codewords is denoted by A_q(n,d).


 §.§ Linear Functions


	
	A function f : 𝔽_q^k→𝔽_q^l is said to be linear if it satisfies the following condition:
	
    f(α𝐱 + β𝐲) = α f(𝐱) +β f(𝐲), ∀𝐱,𝐲∈𝔽_q^k and α , β∈𝔽_q

	It can be expressed as a matrix operation
	
    f(𝐱) = 𝐅𝐱,  for some 𝐅∈𝔽_q^l × k.


The kernel of f or the null space of 𝐅 is denoted by ker(f). For the rest of the paper, the considered function is such that l ≤ k and 𝐅 is full rank, i.e., rank_𝔽_q(𝐅)=l.
We denote the range of f as Im(f) = 𝔽_q^l≜{f_0,f_1, f_q^l-1}.


	Consider a linear function  f:𝔽_q^k→𝔽_q^l. We define |ker(f)|_d to be the number of vectors in ker(f) of Hamming weight d.


	Consider a linear function  f:𝔽_q^k→𝔽_q^l. We define 𝔽_q^k/ker(f) to be the set of all cosets of ker(f) in 𝔽_q^k.




	
	Consider a linear function f : 𝔽_q^k→𝔽_q^l. The cosets in 𝔽_q^k/ker(f) partion 𝔽_q^k, where the elements of each coset are assigned to a unique function value, i.e there is an induced isomorphism f̃ : 𝔽_q^k/ker(f) →𝔽_q^l such that 𝐮 + ker(f) ↦ f(𝐮).
We use f̅_̅i̅ to denote the coset mapped to f_i∈𝔽_q^l and f̅_̅0̅ to denote ker(f).	


Due to linearity, the distance distribution of f̅_̅i̅∀ i ∈𝔽_q^l is the same and is equal to the weight distribution of ker(f).



 §.§ Function-Correcting Codes



The system model illustrated in Fig. <ref> consists of a transmitter that wants to send a vector 𝐮∈𝔽_q^k. The receiver wants to evaluate a linear function f : 𝔽_q^k→𝔽_q^l at 𝐮. 
The transmitter encodes the data using a systematic encoding
𝔈 : 𝔽_q^k→𝔽_q^k+r such that 𝔈(𝐮) = (𝐮,𝐩).

The encoded data 𝔈(𝐮) is sent over a channel that can introduce upto t symbol errors. The receiver receives 𝐲 = 𝔈(𝐮)+𝐞∈𝔽_q^k+r ,w_H(𝐞) ≤ t.
The receiver has a decoding function 𝔇 : 𝔽_q^k+r→𝔽_q^k, 
 which satisfies 𝔇(𝐲) = f(𝐮) ∀ u ∈𝔽_q^k.  




The definition for an FCC was given in <cit.>. 

	
	<cit.> An encoding 𝔈 : 𝔽_q^k→𝔽_q^k+r is said to be an (f, t)-FCC for a function f : 𝔽_q^k→𝔽_q^l if for all 𝐮_i,𝐮_j∈𝔽_q^k with f(𝐮_i)  f( 𝐮_j),

	
    d_H(𝔈(𝐮_i),𝔈(𝐮_j)) ≥ 2t+1.
  
	
	
	




	When the function f:𝔽_q^k →𝔽_q^k is a bijection, an (f,t)-FCC is equivalent to a systematic (n,q^k,2t+1) code. 


	
	<cit.>
	The optimal redundancy r_f(k,t) is defined as the smallest r possible such that there exists an (f, t)-FCC with an encoding function 𝔈 : 𝔽_q^k→𝔽_q^k+r.



The distance requirement matrix was introduced in <cit.>.

	
	<cit.>
	Let, 𝐮_0, 𝐮_1𝐮_q^k-1∈𝔽_q^k.  
	The distance requirement matrix 𝐃_f(t,𝐮_0, 𝐮_1𝐮_q^k-1) for an (f, t)-FCC is a q^k× q^k matrix with entries
	
		
    [𝐃_f(t,𝐮_0, 𝐮_q^k-1)]_ij=
    		
    			
    			[2t+1 - d_H(𝐮_i,𝐮_j)]^+;     if f(𝐮_i)  f( 𝐮_j)
    
    			0;    otherwise.

	
 

For linear functions, we use the shorthand 𝐃_f(t) 𝐃_f(t,𝐮_0, 𝐮_1𝐮_q^k-1).


	
	For a linear function f : 𝔽_q^k→𝔽_q^l, ker(f) has a dimension of k-l over 𝔽_q. So, each column of 𝐃_f(t) will have at least q^k-l  number of 0s, since the cosets in 𝔽_q^k/ker(f) are of the same cardinality and all the elements of a particular coset are mapped to the same element in 𝔽_q^l.
	
	



	
	Since 𝔽_q^k is a vector space over 𝔽_q, the distance distribution is same as the weight distribution. As a result, the columns (and rows) of 𝐃_f(t) are permutations of each other.
	
	


Irregular-distance codes of constraint 𝐃 were defined in <cit.> as follows:
<cit.>
	Let 𝐃∈ℕ_0^M× M. Then P = {𝐩_i : i∈ [M] } is said to be an irregular-distance code of constraint 𝐃 or a 𝐃-code if there is an ordering of P such that d_H(𝐩_i,𝐩_j) ≥ [𝐃]_ij∀ i,j ∈ [M].
	
	Further, N_q(𝐃) is defined as the smallest integer r such that there exists a 𝐃-code of length r over 𝔽_q.

We can thus see that an (f,t)-FCC is an irregular-distance code with 𝐃= 𝐃_f(t,𝐮_0, 𝐮_1𝐮_q^k-1). 

It is shown in <cit.> that the problem of constructing an FCC can be formulated as that of finding sufficiently large independent sets of the following graph. 

	<cit.>
	We define 𝒢_f(t,k,r) as the graph with vertex set V = 𝔽_q^k×𝔽_q^r such that any two vertices 𝐯_i = (𝐮_i,𝐫_i) and 𝐯_j = (𝐮_j,𝐫_j) are connected if and only if
	
		
  * 𝐮_i = 𝐮_j, or
		
  * f(𝐮_i)  f(𝐮_j) and d_H(𝐯_i,𝐯_j) ≤ 2t+1.
	
	  


That is, if two vertices (𝐮_𝐢,𝐯_𝐢)  and  (𝐮_𝐣,𝐯_𝐣) are connected in 𝒢_f(t,k,r), then an (f,t)-FCC cannot contain both (𝐮_𝐢,𝐯_𝐢)  and  (𝐮_𝐣,𝐯_𝐣) as codewords. So if we can find an independent set of the graph of size q^k, it can be used as an (f,t)-FCC.

	
	Let the vertex set of 𝒢_f(t,k,r) be V = {𝐯_1,𝐯_2,,𝐯_q^k+r}.
	The adjacency matrix 𝐆 of graph 	𝒢_f(t,k,r) is a q^k+r× q^k+r matrix such that
	
    [𝐆]_i,j =
    		
    			
    			1;   if 𝐯_i and 𝐯_j are connected
    
    			0;    otherwise.


We use γ_f(k, t) to denote the smallest integer r such that there
exists an independent set of size q^k
in 𝒢_f(t,k,r).


	
	Consider the function f:𝔽_2^2→{0,1} defined as f((u_1u_2)) = u_1∪ u_2, where ∪ denotes the logical OR operator. The graph 𝒢_f(t,k,r) for t=1 and r=2 is shown in Fig. <ref>.


The following theorem from <cit.> shows the connection between the redundancy of optimal FCCs, irregular-distance codes and independent sets of 𝒢_f(t,k,r).

	<cit.> For any function f:𝔽_q^k→𝔽_q^l,    
	
    r_f(k,t) = γ_f(k, t) = N(𝐃_f(t))
  

We can thus see that an (f,t)-FCC is an irregular-distance code with 𝐃= 𝐃_f(t,𝐮_0, 𝐮_1𝐮_q^k-1). 

The definitions for function distance and function distance matrix as in <cit.> are given below:

	<cit.>
	
	For a function f:𝔽_q^k→𝔽_q^l, the distance between f_i, f_j∈ Im(f) = 𝔽_q^l is defined as 
	
    d_f(f_i,f_j)≜min_𝐮_i,𝐮_j∈𝔽_q^kd_H(𝐮_i,𝐮_j),  s.t.f(𝐮_i)=f_i, f(𝐮_j)=f_j.



	<cit.>
	
	The function distance matrix of a function f:𝔽_q^k→𝔽_q^l  is a q^l× q^l matrix with its entries given by
	
    [𝐃_f(t,f_0, f_1 f_q^l-1)]_ij =
    		
    			
    			[2t+1 - d_f(f_i,f_j)]^+;   if i  j
    
    			0;    otherwise.




	
	It follows from Remarks <ref> and <ref> that the problem of finding function distances becomes that of finding inter-coset distances. We also have,
    d_f(f_i,0) =w_H(f̅_̅i̅) =min_𝐮∈f̅_̅i̅w_H(𝐮).

	Because of the property of cosets, the inter-coset distance distributions are uniform, i.e. the column/row entries of 	𝐃_f(t,f_0, f_1 f_q^l-1) are from the set {d_f(f_i,0); f_i∈𝔽_q^l}, i.e, the columns (and rows) are permutations of each other.


	
	Consider functions f and g such that f(𝐱) = 𝐅𝐱 and g(𝐱) = 𝐆𝐱. Then the distance requirement matrix (and function distance matrix) for f and g are the same if 𝐅 can be obtained from 𝐆 using only elementary row operations and column permutations.

The following lower bound on redundancy is given in <cit.>.

	
	<cit.> For any function f:𝔽_q^k→𝔽_q^l and {𝐮_1, 𝐮_2𝐮_M}⊆𝔽_q^k
	
    r_f(k,t) ≥ N_q(𝐃_f(t,𝐮_1, 𝐮_2𝐮_M)
  
	and for |Im(f)| ≥ 1
	
    r_f(k,t) ≥ 2t.
  



As shown in <cit.>, an existential bound on redundancy is obtained on doing coset-wise coding, i.e., when the same parity vector is assigned to all the messages in one coset.

	
	<cit.> For any function f:𝔽_q^k→𝔽_q^l,  
	
    r_f(k,t) ≤ N(𝐃_f(t,f_0, f_1 f_q^l-1))
  
	where 𝐃_f(t,f_0, f_1 f_q^l-1) is the function distance matrix.


The bound in Theorem <ref> can be tight as shown in the following corollary which follows from Theorems <ref> and <ref>.

	
	 If there exists a set of representative information vectors {𝐮_0, 𝐮_1𝐮_q^l-1} with {f(𝐮_0) f(𝐮_q^l-1)} = Im(f) and 
	 
    𝐃_f(t,f_0, f_1 f_q^l-1) = 𝐃_f(t,𝐮_0, 𝐮_1𝐮_q^l-1),

	 then
	
    r_f(k,t) = N(𝐃_f(t,f_0, f_1 f_q^l-1)).

	
	

We propose a class of linear functions for which such a selection of representative vectors exists in Section <ref>.

A generalized version of the Plotkin bound for binary FCCs is provided in <cit.>.

	
	For any distance requirement matrix 𝐃∈ℕ_0^M× M,
	
    N_2(𝐃) ≥4/M^2∑_i,j:i<j^[𝐃]_ij,    if M is even
    4/M^2-1∑_i,j:i<j^[𝐃]_ij,    if M is odd.




	
	Consider a function f : 𝔽_2^4→𝔽_2^2 with the mapping 
    𝐱↦[ 1 1 1 0; 0 1 1 0 ]𝐱
.
 


The coset decomposition 𝔽_2^4/ker(f) and the induced mapping is: 

    {0000, 0001, 0110, 0111}↦ 00
       {0010, 0011, 0100, 0101}↦ 11
       {1000, 1001, 1110, 1111}↦ 10
       {1100, 1101, 1010, 1011}↦ 01.

The distance requirement matrix for an (f,t)-FCC is

𝐃_f(t,u_0, u_1 u_15) =(2t+1)𝐈_16-

    [ 0 0 1 2 1 2 0 0 1 2 2 3 2 3 3 4; 0 0 2 1 2 1 0 0 2 1 3 2 3 2 4 3; 1 2 0 0 0 0 1 2 2 3 1 2 3 4 2 3; 2 1 0 0 0 0 2 1 3 2 2 1 4 3 3 2; 1 2 0 0 0 0 1 2 2 3 3 4 1 2 2 3; 2 1 0 0 0 0 2 1 3 2 4 3 2 1 3 2; 0 0 1 2 1 2 0 0 3 4 2 3 2 3 1 2; 0 0 2 1 2 1 0 0 4 3 3 2 3 2 2 1; 1 2 2 3 2 3 3 4 0 0 1 2 1 2 0 0; 2 1 3 2 3 2 4 3 0 0 2 1 2 1 0 0; 2 3 1 2 3 4 2 3 1 2 0 0 0 0 1 2; 3 2 2 1 4 3 3 2 2 1 0 0 0 0 2 1; 2 3 3 4 1 2 2 3 1 2 0 0 0 0 1 2; 3 2 4 3 2 1 3 2 2 1 0 0 0 0 2 1; 3 4 2 3 2 3 1 2 0 0 1 2 1 2 0 0; 4 3 3 2 3 2 2 1 0 0 2 1 2 1 0 0;   ].

The function distance matrix is given by



    𝐃_f(t,f_0, f_1, f_2, f_3) =
    (2t+1)𝐈_4-[ 0 1 1 2; 1 0 2 1; 1 2 0 1; 2 1 1 0 ].


If we choose a set of representative vectors {u_0, u_1,u_2,u_3} = {0000,0100,1000,1100}, we can see that 𝐃_f(t,f_0, f_1, f_2, f_3) = 𝐃_f(t,𝐮_0, 𝐮_1, 𝐮_2, 𝐮_3). So, by Corollary <ref>, N_2(𝐃_f(t,f_0, f_1, f_2, f_3))=N_2(𝐃_f(t,𝐮_0, 𝐮_1𝐮_15)). That is, the simplified problem of coset-wise coding in 2 dimensions can attain the optimal redundancy for the original problem of dimension 4.





§ MAIN RESULTS


In this section, we provide our main results. We propose a lower bound on the redundancy of an FCC. When the function considered is a bijection, we obtain a bound for classical systematic ECCs . For linear functions, we show that the bound provided in Lemma <ref> simplifies and can be obtained in terms of the weight distribution of the kernel of the function. We show that the adjacency matrix of the graph 𝒢_f(t,k,r) has a recursive block circulant structure for linear functions. For functions whose domain is a vector space over a finite field of characteristic 2, we characterise the spectrum of the adjacency matrix, leading to lower bounds on redundancy. We consider the case of coset-wise coding and identify functions for which coset-wise coding is optimal.



 §.§ A Lower Bound on Redundancy


We provide a lower bound on the redundancy required for the case when 2t+1 ≤ k. We consider a graph G'_f(t,k,r) with the same vertex set as of 𝒢_f(t,k,r) such that its maximum independent set contains the maximum independent set of 𝒢_f(t,k,r). This leads to an upper bound on α(𝒢_f(t,k,r)), which gives a lower bound on the redundancy required.


	
	For a function f: 𝔽_q^k→ Im(f) and t ∈ℕ such that 2t+1 ≥ k, there exists an (f,t)-FCC of redundancy length r only if
		
    q^r≥q^k/α(𝒢_f(t,k,0)).




	Consider the graph 𝒢_f(t,k,0) with vertex set 𝔽_q^k. Two vertices 𝐱_1,𝐱_2∈𝔽_q^k are connected if and only if f(𝐱_1)=f(𝐱_2) and d_H(𝐱_1,𝐱_2)<2t+1. Let ℛ be a graph with vertex set 𝔽_q^r such that any two distinct vertices are connected. Note that α(ℛ)=1. Let G'_f(t,k,r) be the Cartesian product of the graphs 𝒢_f(t,k,0) and ℛ, i.e.,
	
	
    G'_f(t,k,r) = 𝒢_f(t,k,0) ℛ.
An illustration is provided in Example <ref>.
	The vertex set of 𝒢_f(t,k,r) is the same as that of G'_f(t,k,r).
	
	Now, we show that if two vertices are unconnected in 𝒢_f(t,k,r), then they are unconnected in G'_f(t,k,r). Let, (𝐱_i,𝐯_i) and (𝐱_j,𝐯_j) ∈𝔽_q^k+r be connected in G'_f(t,k,r). This happens if and only if 
		
  * 𝐱_i=𝐱_j, or 
		
  * d_H(𝐱_i,𝐱_j)<2t+1 and 𝐯_i=𝐯_j.
	 
	Consider condition (i). If 𝐱_i=𝐱_j, then (𝐱_i,𝐯_i) and (𝐱_j,𝐯_j) are connected in 𝒢_f(t,k,r) by definition. Consider condition (ii). If d_H(𝐱_i,𝐱_j)<2t+1 and 𝐯_i=𝐯_j, then d_H((𝐱_i,𝐯_i),(𝐱_j,𝐯_i))<2t+1, which implies that (𝐱_i,𝐯_i) and (𝐱_j,𝐯_i) are connected in 𝒢_f(t,k,r). Hence, any α-set of 𝒢_f(t,k,r) is a subset of some independent set of G'_f(t,k,r), which implies that 
	
    α(𝒢_f(t,k,r)) ≤α(G'_f(t,k,r)).

	
	Now, we bound the independence number of G'_f(t,k,r). Since G'_f(t,k,r) = 𝒢_f(t,k,0) ℛ, from <cit.> and <cit.>, we can use the upper bound on the independence number of a graph Cartesian product: 
	
	
	
    α(G'_f(t,k,r)    ≤ min{q^k·α(ℛ), q^r·α(𝒢_f(t,k,0))}
       = min{q^k, q^r·α(𝒢_f(t,k,0))}.

	For an (f,t)-FCC of length r to exist, α(𝒢_f(t,k,r)) should be q^k. So, from (<ref>) and (<ref>), we can say that if an (f,t)-FCC of length r exists, then 
    q^r·α(𝒢_f(t,k,0))≥ q^k,

	which gives the required result.


The result of Theorem <ref> can be used to get a lower bound on the parity required for classical systematic ECCs by considering the function f to be a bijection.

	
	There exists a (q^k+r,q^k,d) systematic block code where d-1/2≤ k only if
	
    q^r≥q^k/A_q(k,d),

	where A_q(k,d) is the maximum number of codewords in any q-ary code of length k and minimum distance d.


	If d is odd, take t= d-1/2. When the function f is a bijection, the independent sets of 𝒢_f(t,k,0) will be the sets of vectors in 𝔽_q^k such that the Hamming distance between them is at least 2t+1, which implies that the cardinality of the α-set will be α(𝒢_f(t,k,0)) = A_q(k,2t+1). A similar argument can be used for the case when d is even to get the required result.
	

	
	Consider the function f:𝔽_2^3→{0,1} defined as f((u_1u_2u_3)) = u_1∪ u_2∪ u_3. Let t=1. For r=1, consider the graph ℛ with vertex set 𝔽_2 with the two elements in 𝔽_2 being connected. Consider the graph 𝒢_f(t,k,0) with vertex set 𝔽_2^3 such that any two vertices 𝐱_i and 𝐱_j are connected if and only if f(𝐱_i) f(𝐱_j) and d_H(𝐱_i,𝐱_j)<3. Their Cartesian Product G'_f(t,k,r) = 𝒢_f(t,k,0) ℛ is shown in Fig. <ref>.




 §.§ Linear-Function Correcting Codes  


As mentioned in Remarks <ref> and <ref>, linearity imposes a structure on the distance requirement matrix and function distance matrix of an FCC. This simplifies the bounds proposed in <cit.> and gives rise to new bounds as shown in this section.

Now, for linear functions, we show that the Plotkin bound for FCCs provided in Lemma <ref> can be simplified and can be made more computationally efficient to calculate. 

	

	
	For a linear function f:𝔽_q^k→𝔽_q^l, the optimal redundancy of an (f, t) FCC
	
    r_f(k, t) ≥ (q/q-1)(2t+1)(1-q^-l)-k+s/(q-1)(q^k-1),
  
	where s = ∑_x∈ ker(f)w_H(x) i.e, the sum of Hamming weights of the vectors in ker(f).


	The bound can be obtained by counting ∑_i≤ j^d_H(𝐩_i,𝐩_j) in two different ways.
	Let 𝐃 =  𝐃_f(t) be the distance requirement matrix for the function f.
	
	Let 𝐩_1, 𝐩_2, 𝐩_q^k be the codewords of a 𝐃-code of length r. Arrange the codewords as a q^k× r matrix 𝐏. Since each column of 𝐏 can contribute at most q^2k(1 - 1/q) to the sum ∑_i, j^d_H(𝐩_i,𝐩_j), we have 
	
    ∑_i, j^d_H(𝐩_i,𝐩_j) ≤ rq^2k-1(q-1).

	
	Furthermore, by definition,
	
    d_H(𝐩_i,𝐩_j) ≥ [𝐃]_ij,

	which implies that
	
    ∑_i, j^d_H(𝐩_i,𝐩_j) ≥∑_i, j^[𝐃]_ij.

	Note that dim_𝔽_q(ker(f)) = k-l. Thus, there will be at least q^k-l 0s in each column. Because of linearity, the sum of non-zero entries of each column will be the same. Thus,
	
    ∑_i, j^[𝐃]_ij   = (no. of columns)×(sum of one column).

	To find the sum of one column, consider the first column of 𝐃. Let I be the row indices of the non-zero entries in the first column of 𝐃. Let the first column correspond to the all zero vector 0. From the definition of 𝐃_f(t) and Remark <ref>, we have
		
    [𝐃]_i1   ≥ 2t+1 - d_H(𝐮_i,0)
       = 2t+1 - w_H(𝐮_i).

	This implies that
	
    ∑_i^ [𝐃]_i1≥ (2t+1)(q^k-q^k-l) - ∑_i ∈ I^ w_H(u_i).

	The sum of weights of all the vectors in 𝔽_q^k can be found to be k(q-1)q^k-1. Let the sum of weights of the vectors in ker(f) be s, which gives
	
	
    ∑_i^ [𝐃]_i1   ≥ (2t+1)(q^k-q^k-l) - k(q-1)q^k-1 + s.

	Thus,
	
    ∑_i≤ j^[𝐃]_ij   ≥q^k×∑_i^ [𝐃]_i1
       = q^k((2t+1)(q^k-q^k-l) - k(q-1)q^k-1 + s.

	
	From (<ref>), (<ref>) and (<ref>), we get the required result.

 The Plotkin bound provided in <cit.> requires the sum of all [𝐃]_ij to calculate the bound. For linear functions, we can see that we require only the sum of the Hamming weights of the vectors in ker(f).
 
We now consider the structure linearity imposes on the graph 𝒢_f(t,k,r). We show that its adjacency matrix 𝐆 has a recursive block circulant structure. 

	For some 𝐮 = (u_1u_2 u_m)∈𝔽_q^m and m ∈ [n]∪{0}, define U_m^n ≜{(x_1x_2 x_n)∈𝔽_q^n: (x_1x_2 x_m)=(u_1u_2 u_m)} if m  0 and U_m^n= 𝔽_q^n if m=0. 
	

That is, U_m^n is the set of all n length vectors in 𝔽_q such that its first m indices is equal to 𝐮.

	
	For a linear function f:𝔽_q^k→𝔽_q^l, let 𝐆∈{0,1}^q^n× q^n, where n k+r, be the adjacency matrix of the graph 𝒢_f(t,k,r). Let the rows and columns of the matrix 𝐆 be indexed by the vectors in 𝔽_q^n. Then, 𝐆 satisfies the following condition:
	
	
		
  C1 For all 𝐮_m,𝐯_m∈𝔽_q^m and for all m ∈ [n]∪{0}, for some ordering of  U_m^n and V_m^n, if the submatrix 𝐒𝐆_U_m^n,V_m^n is expressed in block matrix form as
	
    𝐒 = [ 𝐒_1,1 𝐒_1,2       𝐒_1,q; 𝐒_2,1 𝐒_2,2       𝐒_2,q;     ⋮     ⋮     ⋱     ⋮; 𝐒_q,1 𝐒_q,2       𝐒_q,q;       ],

	where 𝐒_i,j is of order q^n-m-1, then for any i,j ∈ [q], 
    𝐒_i,j = 𝐒_<i+1>_q,<j+1>_q = ∀i,j∈[q].

	


	 Consider the case when q is a prime number p. For any non-negative integer i ≤ p, we use 𝐢_p^n to denote the n length p-ary representation of i. We have to show that for all m ∈ [n]∪{0} and for all 𝐮_m,𝐯_m∈𝔽_p^m, the submatrix 𝐆_U_m^n,V_m^n satisfies condition C1. Assume that U_m^n and V_m^n are ordered lexicographically. For an ordered set U, let U(i) represent the ith element in this ordering.
	
	Consider the matrix 𝐆' ∈ℕ_0^p^n× p^n defined as [𝐆']_ij=d_H(𝐢_p^n,𝐣_p^n). We can express  𝐒' = 𝐆'_U_m^n,V_m^n as
	
    𝐒' = [ 𝐒'_1,1 𝐒'_1,2        𝐒'_1,p; 𝐒'_2,1 𝐒'_2,2        𝐒'_2,p;      ⋮      ⋮      ⋱      ⋮; 𝐒'_p,1 𝐒'_p,2        𝐒'_p,p;        ],
where 𝐒'_i,j∈{0,1}^p^n-m-1× p^n-m-1∀i,j ∈ [2]. It is evident that 
	
    [𝐒_k,l']_ij =
    		
    			d_H(U_m^n(i),V_m^n(j));    k=l
     d_H(U_m^n(i),V_m^n(j))+1;    k  l.

	Thus, 𝐆_n' satisfies condition C1. 
	
	Now, consider the matrix 𝐆” defined as 
	
    [𝐆”]_ij =
    		
    			
    			1;    if  	[𝐆']_ij≤ 2t+1
    
    			0;    otherwise.

	We can see that 𝐆” will also satisfy condition C1 as it is obtained by thresholding the entries of 𝐆'. The adjacency matrix 𝐆 can be obtained from 𝐆” as 
	
    [𝐆]_i_p^n,j_p^n =
    		
    			
    			0;    if 𝐢_p^n[1:k] - 𝐣_p^n[1:k] ∈ ker(f)	 
    
    			[𝐆”]_ij;      otherwise.

	
	
	
	To show that 𝐆 satisfies condition C1, it is now enough to show that for for all m ∈ [n]∪{0} and for all 𝐮_m,𝐯_m∈𝔽_p^m, the submatrix 𝐆_U_m^n,V_m^n satisfies the following condition:
	
    [𝐆_U_m^n,V_m^n]_𝐢_p^n,𝐣_p^n=0  [𝐆_U_m^n,V_m^n]_𝐠_p^n,𝐡_p^n=0

	where 𝐠_p^n = 𝐢_p^n+a·𝐞_m+1(mod (n-m)) and 𝐡_p^n = 𝐣_p^n+a·𝐞_m+1(mod (n-m)), where a ∈𝔽_p. 
	
	From the definition of 𝐆, we know that [𝐆]_𝐢_p^n,𝐣_p^n=0 if and only if 
	
		
  * f(𝐢_p^n[1:k])  f(𝐣_p^n[1:k]) and d_H(𝐢_2^n,𝐣_2^n) ≥ 2t+1, or
		
  * 𝐢_p^n[1:k] 𝐣_p^n[1:k] and f(𝐢_p^n[1:k]) = f(𝐣_p^n[1:k]).
	
	Since 𝐆 is obtained from 𝐆”, for all 𝐢_p^n and 𝐣_p^n satisfying the first condition, [𝐆_U_m^n,V_m^n]_𝐢_p^n,𝐣_p^n=0  [𝐆_U_m^n,V_m^n]_𝐠_p^n,𝐡_p^n=0, as 𝐠_p^n[1:k] and 𝐡_p^n[1:k] lie in different cosets of 𝔽_p^k/ker(f) and d_H(𝐠_p^n,𝐡_q^n) = d_H(𝐢_q^n,𝐣_q^n). Now, consider 𝐢_q^n and 𝐣_q^n satisfying the second condition, i.e., 𝐢_q^n[1:k] 𝐣_q^n[1:k] and 𝐢_q^n[1:k]-𝐣_q^n[1:k] ∈ ker(f). Then, from the property of cosets, 𝐠_q^n[1:k]-𝐡_q^n[1:k] ∈ ker(f). That is for such 𝐢_p^n and 𝐣_p^n, [𝐆_U_m^n,V_m^n]_𝐢_p^n,𝐣_p^n=0  [𝐆_U_m^n,V_m^n]_𝐠_p^n,𝐡_p^n=0. Thus, 𝐆 satisfies condition C1.
	
	When q is a prime power, i.e., q = p^m, for some prime p, 𝔽_q^k is isomorphic to the vector space 𝔽_p^mk. So the same arguments can be considered where the matrix 𝐆 is indexed by the vectors in 𝔽_p^mk.



	
	Equivalently the structure of 𝐆 can be seen as follows: express 𝐆 in block matrix form as 
    𝐆 = [ 𝐆_1,1 𝐆_1,2       𝐆_1,q; 𝐆_2,1 𝐆_2,2       𝐆_2,q;     ⋮     ⋮     ⋱     ⋮; 𝐆_q,1 𝐆_q,2       𝐆_q,q;       ].
Let 𝐆_i𝐆_1,i Then 𝐆 will be of the form 
    𝐆 = [   𝐆_1   𝐆_2   𝐆_3       𝐆_q-1   𝐆_q;   𝐆_q   𝐆_1   𝐆_2       𝐆_q-2 𝐆_q-1; 𝐆_q-1   𝐆_q   𝐆_1       𝐆_q-3 𝐆_q-2;     ⋮     ⋮     ⋮     ⋱     ⋮     ⋮;   𝐆_3   𝐆_4   𝐆_5         𝐆_1   𝐆_2;   𝐆_2   𝐆_3   𝐆_4         𝐆_q   𝐆_1;       ].
Note that the matrix 𝐆 is symmetric as it is an adjacency matrix. Thus, 𝐆 is a symmetric block circulant matrix. The submatrices 𝐆_1, 𝐆_2 , 𝐆_q can further be divided into their submatrices recursively and the block circulant structure will hold.



	
	Consider the adjacency matrix 𝐆∈{0,1}^2^nm× 2^nm corresponding to a function f: 𝔽_2^m^k→𝔽_2^m^l. Let the rows and columns of the matrix 𝐆 be indexed by the set of vectors 𝔽_2^nm in lexicographic order. Then 𝐆 satisfies the following condition: 
		
  C1 For all 𝐮_i,𝐯_i∈𝔽_2^i and for all i ∈ [nm]∪{0}, if the submatrix 𝐒𝐆_U_i^nm,V_i^nm is expressed in block matrix form as
	
    𝐒 = [ 𝐒_1,1 𝐒_1,2; 𝐒_2,1 𝐒_2,2 ],

	where 𝐒_i,j∈{0,1}^2^n-m-1× 2^n-m-1∀i,j ∈ [2], then 𝐒_1,1 = 𝐒_2,2 and 𝐒_1,2=𝐒_2,1.
	
	



	Equivalently the structure of 𝐆 can be seen as follows: express 𝐆 in block matrix form as 
    𝐆 = [ 𝐆_1,1 𝐆_1,2; 𝐆_2,1 𝐆_2,2 ].

	Then 𝐆_1,1 = 𝐆_2,2 and 𝐆_1,2=𝐆_2,1.
	The submatrices 𝐆_1,1,   𝐆_1,2, 𝐆_2,1 and 𝐆_2,2 can further be divided into their submatrices recursively and the above condition will hold. The upshot is that 𝐆 can be fully specified using just its first row.

We now characterise the spectrum of the adjacency matrix of 𝒢_f(t,k,r).


	
	A q^n× q^n matrix 𝐌 satisfying condition C1 is diagonalised by 𝐖_q^⊗ n, where 𝐖_q is the qth order DFT matrix.


	Let ℳ_n⊆ℂ^q^n× q^n be the set of q^n× q^n matrices satisfying condition C1. We can use an induction based argument to prove the claim. We can see that ℳ_1 is the set of all circulant matrices of order q. The DFT matrix 𝐖_q diagonalises all the matrices in ℳ_1. Now, consider the induction hypothesis: 𝐖_q^⊗ n diagonalises all the matrices in ℳ_n. We have to show that 𝐖_q^⊗ n+1 diagonalises all 𝐌∈ℳ_n+1.
	
	Define the matrix 𝐉_i∈ℳ_1 as [𝐉_i]_1k = 1 if k=i and 0 otherwise, i.e., 𝐉_i is the q× q circulant matrix with its first row equal to 𝐞_i. Consider any 𝐌∈ℳ_n+1, which is of the form
	
	
    𝐌 = [   𝐌_1   𝐌_2   𝐌_3       𝐌_q-1   𝐌_q;   𝐌_q   𝐌_1   𝐌_2       𝐌_q-2 𝐌_q-1; 𝐌_q-1   𝐌_q   𝐌_1       𝐌_q-3 𝐌_q-2;     ⋮     ⋮     ⋮     ⋱     ⋮     ⋮;   𝐌_3   𝐌_4   𝐌_5         𝐌_1   𝐌_2;   𝐌_2   𝐌_3   𝐌_4         𝐌_q   𝐌_1;       ].

	Using remark <ref>, we can express 𝐌 as 𝐌= ∑_i=1^q𝐉_i⊗𝐌_i, where 𝐌_i∈ℳ_n∀ i∈[q]. Then,
	
    (𝐖_q^⊗ n+1)^†𝐌(𝐖_q^⊗ n+1)    = ∑_i=1^q(𝐖_q^⊗ n+1)^†(𝐉_i⊗𝐌_i)(𝐖_q^⊗ n+1)
       =∑_i=1^q(𝐖_q^†𝐉_i𝐖_q)((𝐖_q^⊗ n)^†𝐌_i𝐖_q^⊗ n).

	By the induction hypothesis, the above sum is a diagonal matrix. Thus, 𝐖_q^⊗ n+1 diagonalises all 𝐌∈ℳ_n+1. Hence, proved.

Recall that the Hadamard matrix 𝐇_2 = 𝐖_2 and 𝐇_2^n = 𝐇_2^⊗ n. Thus, Corollary <ref> and Theorem <ref> leads to the following result.



	
	
	For a linear function f:𝔽_2^m^k→𝔽_2^m^l, the adjacency matrix 𝐆 of the graph 𝒢_f(t,k,r) is a 2^mn× 2^mn matrix that has the columns of 𝐇_2^mnas its eigen vectors.

The spectrum of 𝐆  can be used to get bounds on its independence number as shown in <cit.>.




	
	<cit.>For the graph 𝒢_f(t,k,r) with q=2^m, m∈ℕ, the independence number 
    α≤-q^k+rλ_min(r)/λ_max(r)-λ_min(r),
 where λ_max(r) and λ_min(r) denote the maximum and minimum eigen values respectively of the adjacency matrix of 𝒢_f(t,k,r).

Note that for any graph, the least eigen value is non-positive and is 0 only when there are no edges in the graph.

Theorem <ref>, Corollary <ref> and the fact that we need an independent set of size q^k, can be used to get a lower bound on r_f(k,t) as shown in the following corollary.

	
	The minimum redundancy r_f(k,t) of an (f,t)-FCC satisfies the following inequality: 
    q^r_f(k,t)≥ 1-λ_max(r)/λ_min(r),
 where λ_max(r) and λ_min(r) denote the maximum and minimum eigen values respectively of the adjacency matrix of 𝒢_f(t,k,r).

	



	Consider a function f: 𝔽_2^3→𝔽_2^2, defined as f(𝐮) = [ 0 1 1; 1 1 0 ]𝐮.
	For t=1 and r =1 the adjacency matrix 𝐆 of the graph 𝒢_f(t,k,r) is 𝐆=
	
    [[ 0 1 1 1 1 1 1 0 1 1 1 0 1 0 0 0; 1 0 1 1 1 1 0 1 1 1 0 1 0 1 0 0; 1 1 0 1 1 0 1 1 1 0 1 1 0 0 1 0; 1 1 1 0 0 1 1 1 0 1 1 1 0 0 0 1; 1 1 1 0 0 1 1 1 1 0 0 0 1 1 1 0; 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 1; 1 0 1 1 1 1 0 1 0 0 1 0 1 0 1 1; 0 1 1 1 1 1 1 0 0 0 0 1 0 1 1 1; 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 0; 1 1 0 1 0 1 0 0 1 0 1 1 1 1 0 1; 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1; 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 1; 1 0 0 0 1 1 1 0 1 1 1 0 0 1 1 1; 0 1 0 0 1 1 0 1 1 1 0 1 1 0 1 1; 0 0 1 0 1 0 1 1 1 0 1 1 1 1 0 1; 0 0 0 1 0 1 1 1 0 1 1 1 1 1 1 0 ]].
The structure specified in Corollary <ref> can be seen in the above adjacency matrix.


 

 §.§ Coset-wise Coding

 
 In coset-wise coding all the message vectors in a particular coset in 𝔽_q^k/ker(f) are given the same parity vector. As shown in Theorem <ref>, for such a coding scheme, the distance constraint
 is specified by the function distance matrix, 𝐃_f(t,f_0, f_1 f_q^l-1). For a linear function f : 𝔽_q^k→𝔽_q^l, there is a reduction in the dimension
 of the function correction problem from k to l while doing coset-wise coding.
 
 We now propose a lower bound on the parity length N_q(𝐃_f(t,f_0, f_1 f_q^l-1)) using an extension of the sphere
 packing bound.
 
 	
 	For a linear function f:𝔽_q^k→𝔽_q^l with d_f being the minimum Hamming distance of ker(f), the length n of an (f, t)-FCC with coset-wise parity satisfies
 	
 	
    q^n   ≥  q^k[∑_i=0^δni(q-1)^i
       +∑_i=δ+1^tni(q-1)^i - ∑_j=1^2(i-δ)-1a_ij|ker(f)|_(2δ + j)/1+∑_j=2
    j  is even^2(i-δ)|ker(f)|_(2δ+j)]

 	where,
 	
    a_ij = ∑_l=j-i^j-1/22δ+jδ+ln-2δ-ji-j+l(q-1)^δ+2l+i-j
 
 	and δ = d_f-1/2.
 	
 
 
 Let M = q^k be the number of message vectors in 𝔽_q^k. Consider an FCC that encodes 𝐮∈𝔽_q^k to 𝔈(𝐮) ∈𝔽_q^n. Consider a coset f̅_̅i̅∈𝔽_q^k/ker(f). Let 𝔈(f̅_̅i̅) = {𝔈(𝐮): 𝐮∈f̅_̅i̅}. The Hamming spheres B_H(𝔈(𝐮),t) of vectors 𝐮 in f̅_̅i̅ need not be disjoint. Define B_H(f_i,t) ≜⋃_𝐮∈f̅_̅i̅B_H(𝔈(𝐮),t). The necessary condition for t-error function correction is that B_H(f_i,t) should be disjoint for all f_i∈𝔽_q^l. We have,
 
    ⋃_f_i∈𝔽_q^lB_H(f_i,t) ⊆𝔽_q^n,

 which implies,
 
    ∑_f_i∈𝔽_q^l^|B_H(f_i,t)| ≤ q^n.

 Consider the kernel f̅_̅0̅. Because of linearity, it is enough to find a bound on |B_H(f_0,t)| as |B_H(f_i,t)| = |B_H(f_0,t)| ∀ f_i ∈𝔽_q^l.
 Define, W_i≜{𝐯∈𝔽_q^n: w_H(𝐯)=i} and
 
    S_i≜{   𝐯∈𝔽_q^n: d_H(𝐯,c)≥ i ∀𝐜∈f̅_̅0̅
        and  d_H(𝐮,𝐜) = i  for some 𝐜∈f̅_̅0̅}.

 Let δ = d_f-1/2. Note that B_H(f_i,t) = S_0∪ S_1 ... ∪ S_t where 
 S_0, S_1 ... , S_δ are disjoint.
 It is straightforward to see that
 
    | S_0∪ S_1 ... ∪ S_δ| = q^k-l(∑_i=0^δni(q-1)^i).

 We estimate S_δ+1, S_δ+2, ... S_t to get a stronger bound on B_H(f_i,t).
 
 Assume 0 (all zero vector) is a codeword. The number` of codewords that are at a distance δ+i from 0 and at a distance δ+i or greater from the other codewords in 𝔈(f̅_̅0̅) is given by
 
    |W_δ+i∩ S_δ+i|    = |W_δ+i| - ∑_j = 1-i^i-1|W_δ+i∩ S_δ+j|
       ≥nδ+i(q-1)^δ+i - ∑_j=1^2i-1a_ij|ker(f)|_(2δ+j),

 where
 
    a_ij = ∑_l=j-i^j-1/22δ+jδ+ln-2δ-ji-j+l(q-1)^δ+2l+i-j.

 We use a_ij to denote the number of δ+i weight vectors that are at a distance less than δ+i from a particular 2δ+j weight codeword and recall that |ker(f)|_(2δ+j) represents the number of vectors of weight 2δ+j in f̅_̅0̅. 
 
 A vector R in W_δ+i∩ S_δ+i is at a distance of δ+i from say N codewords. It can be verified that these codewords have to be of even weight. Thus, we can say that N is upper bounded by 
 
 
    N ≤ 1 + ∑_j=2
    j  is even^2(i-δ)|ker(f)|_(2δ+j).

 Considering all the codewords corresponding to the vectors in ker(f), we get
 
    |B_H(f_i,t)|    ≥  q^k-l[∑_i=0^δni(q-1)^i
       +∑_i=δ+1^tni(q-1)^i - ∑_j=1^2(i-δ)-1a_ij|ker(f)|_(2δ + j)/1+∑_j=2^2(i-δ)|ker(f)|_(2δ+j)].
  
 Substituting in (<ref>) gives (<ref>).
 
 
 Now, we provide a class of functions for which coset-wise coding is optimal. From Corollaries <ref> and <ref>, coset-wise coding is optimal for a function f, if there is a selection of minimum weight representative vectors from each coset in 𝔽_q^k/ker(f) such that it satisfies (<ref>). Now, we give a class of functions for which such a selection of minimum weight vectors is possible.
 

 



	
	Consider a linear function f:𝔽_q^k→𝔽_q^l. Then 
    𝒮{argmin_𝐮∈f̅w_H(𝐮) : f̅∈𝔽_q^k/ker(f)},

	i.e., 𝒮 is a selection of minimum weight vectors from each coset in 𝔽_q^k/ker(f). Note that 𝒮 is not unique.
	



	
	We define C_f(i) to be the number of cosets in 𝔽_q^k/ker(f) whose minimum weight vector has 1s in i indices and 0s in all the other indices, i.e.,
	
    C_f(i)= |{𝐮∈𝒮: 𝐮 = ∑_j∈ I^𝐞_j  for some  I ⊆ [k], |I|=i}|.









	
	For a linear function f:𝔽_q^k→𝔽_q^l, at least rank(𝐅) cosets in 𝔽_q^k/ker(f) should have a unit vector as its minimum weight vector, i.e., C_f(1)≥ rank(𝐅). 


	Consider the linear function f(𝐱) = 𝐅𝐱. We have, C_f(1)= |{𝐮∈𝒮: 𝐮 = 𝐞_j  for some  j∈ [k]}|.
	The function f maps all the vectors in a particular coset f̅_̅i̅∈𝔽_q^k/ker(f) to the same image f_i∈𝔽_q^l and vectors in distinct cosets will not have the same image. This implies that for some i,j ∈ [k], unit vectors 𝐞_i and 𝐞_j belong to the same coset if and only if the columns 𝐅_(i) and 𝐅_(j) are equal. This implies that the number of distinct non-zero columns of 𝐅 is equal to C_f(1). Since rank(𝐅) cannot be more than the number of distinct non-zero columns of 𝐅, C_f(1) ≥ rank(𝐅).









	
	Consider a linear function f:𝔽_q^k→𝔽_q^l. There exists a selection 𝒮{argmin_𝐮∈f̅w_H(𝐮) : f̅∈𝔽_q^k/ker(f)} that forms a subspace of 𝔽_q^k if and only if exactly l cosets of 𝔽_q^k/ker(f) have a unit vector as its minimum weight vector, i.e., C_f(1) = l.


	For the forward implication, consider a selection 𝒮 which is a subspace of 𝔽_q^k. Note that dim_q𝒮=l. 
	From Lemma <ref>, C_f(1) = l'≥ l. 
	For the sake of contradiction, let l'> l. Then, there exists a set of l' unit vectors in 𝒮, which are independent. This is a contradiction as dim_q𝒮 = l.
	
	For the reverse implication, let C_f(1) = l. Let E = {𝐮∈𝒮: 𝐮 = 𝐞_j  for some  j∈ [k]}. We now show that vectors in span(E) occur in distinct cosets.
	Assume WLOG that E = {𝐞_1, 𝐞_2, 𝐞_3,...,𝐞_l}. Since E is a set of independent vectors, 𝐅E {𝐅𝐞_1, 𝐅𝐞_2, 𝐅𝐞_3,..., 𝐅𝐞_l} is a basis of 𝔽_q^l, the image of f.
	
	Consider 𝐯_1, 𝐯_2∈ span(E). Let 𝐯_1 = ∑_i=1^la_i𝐞_i and 𝐯_2 = ∑_i=1^lb_i𝐞_i, where a_i,b_i ∈𝔽_q ∀ i ∈ [l]. Then,
	
    𝐯_1 and 𝐯_2 are in the same coset
       𝐯_1-𝐯_2∈ ker(f)
       𝐅(𝐯_1-𝐯_2) = 0
       𝐅(∑_i=1^la_i𝐞_i-∑_i=1^lb_i𝐞_i) = 0
       ∑_i=1^la_i𝐅𝐞_i-∑_i=1^lb_i𝐅𝐞_i = 0
        a_i=b_i∀ i ∈ [l]{∵𝐅E  is a basis of 𝔽_q^l}.
 
	
	So, distinct vectors in span(E) are present in distinct cosets. It is easy to verify that the vectors in span(E) are minimum weight vectors in the corresponding cosets. Thus, 𝒮 = span(E).


Thus, for a selection 𝒮 which is a vector space to exist, exactly l cosets should have unit vectors as minimum weight vectors. So, the matrix representation 𝐅 of f must have exactly l distinct non-zero columns. Since rank(𝐅)=l, these columns have to be independent. 
 
 
 Lemmas <ref> and <ref> lead to a class of functions for which the representative vectors satisfy (<ref>) which is given in the following theorem.
 
 	
 	Consider a linear function 
 	
    f : 𝔽_q^k→𝔽_q^l

 	
    𝐮↦𝐅𝐮; 𝐅∈𝔽_q^l × k.

 	There exists a selection of representative vectors {𝐮_0, 𝐮_1𝐮_q^l-1}, where {f(𝐮_0), f(𝐮_1)  f(𝐮_q^l-1)} = Im(f) such that 𝐃_f(t,f_0, f_1 f_q^l-1) = 𝐃_f(t,𝐮_0, 𝐮_1𝐮_q^l-1) if the number of distinct, non-zero, independent columns of 𝐅 is l.
 
 
 	From Remark <ref>, we know that for linear functions, the weight distribution of the vectors in 𝒮={𝐮_0, 𝐮_1𝐮_q^l-1} is the same as {d_f(f_i,0): f_i∈𝔽_q^l}, the intercoset distance distribution. According to Lemma <ref>, there should be exactly l unit vectors in 𝒮 for it to be a vector space and this implies that 𝐅 should have exactly l non-zero distinct columns. Since rank(𝐅) is assumed to be l, the non-zero columns have to be independent. If 𝒮 is a vector space, then its distance distribution will also be uniform, which implies that 𝐃_f(t,f_0, f_1 f_q^l-1) = 𝐃_f(t,𝐮_0, 𝐮_1𝐮_q^l-1).
 	
 	
 
 
The function f given in Example <ref> has exactly 2 distinct, non-zero columns independent over 𝔽_2. We can see that there exists a selection 𝒮 = {0000,0100,1000,1100} which is a subspace of 𝔽_2^4 and 𝐃_f(t,f_0, f_1, f_2, f_3) = 𝐃_f(t,𝐮_0, 𝐮_1, 𝐮_2, 𝐮_3), where 𝒮={𝐮_0, 𝐮_1, 𝐮_2, 𝐮_3)}. 

We now provide a coding scheme for the class of functions specified in Theorem <ref>. Consider a function f : 𝔽_q^k→𝔽_q^l with 𝐅∈𝔽_q^l × k as its matrix representation which has exactly l distinct non-zero independent columns. Choose the set of minimum weight representative vectors 𝒮 ={u_0, u_1u_q^l-1} such that 𝒮 is a subspace of 𝔽_q^k. 
From Corollary <ref>, the optimal redundancy is given by r_f(k,t) = N_2(𝐃_f(t,f_0, f_1 f_q^l-1)) = N_2( 𝐃_f(t,𝐮_0, 𝐮_1𝐮_q^l-1)). Let E be a spanning set of 𝒮. Assume WLOG that E={𝐞_1, 𝐞_2, 𝐞_l}. Then 𝒮 is of the following form:

    𝒮 = {(x_1 x_2 x_k) ∈𝔽_q^k: x_i = 0 ∀i ∈ [l+1:k]}.

Define,

    𝒮' = {(x_1 x_2 x_l): (x_1 x_2 x_l x_k) ∈𝒮}.

Note that 𝒮' ≡𝔽_q^l. 
Let 𝒮' = {𝐮'_0, 𝐮'_1𝐮'_q^l-1}. Note that 𝐃_f(t,𝐮'_0, 𝐮'_1𝐮'_q^l-1) = 𝐃_f(t,𝐮_0, 𝐮_1𝐮_q^l-1). 

Note that the distance requirement matrix 𝐃_f(t,𝐮'_0, 𝐮'_1𝐮'_q^l-1) is the same as the distance requirement matrix for the parity vectors of a classical systematic ECC of cardinality q^l and minimum distance 2t+1 (The parity vectors of a classical systematic ECC can be considered as the parity vectors of an FCC where the function to be corrected is a bijection). So, the parity bits of a systematic (n,q^l,2t+1) block code will be a 𝐃-code where 𝐃 = 𝐃_f(t,𝐮_0, 𝐮_1𝐮_q^l-1).

For the function in Example <ref>, the matrix F = [ 1 1 1 0; 0 1 1 0 ] satisfies the above condition. We can choose 𝒮 = {0000,1000,0100,1100} and 𝒮'={00,01,10,11}≡𝔽_2^2. The function distance matrix is the same as 𝐃_f(t,00,01,10,11). Say, we need an (f,1)-FCC. This is equivalent to the distance constraint that should be satisfied by the parity bits of a block code of cardinality 4 and minimum distance 3. From <cit.>, there exists a (5,4,3) block code. Using the 3 parity bits of this code for coset-wise coding, we have an FCC of r=3. As it is well known from classical coding theory, that non-trivial binary t-error correcting codes of parity length 2t (MDS codes) do not exist, r_f(k,1) ≥ 3. Thus, for the function in Example <ref>, r_f(k,1) = 3.
 
 
 Now, we consider linear functions where coset-wise coding is equivalent to a reduced dimensional classical error correction problem. Consider a linear function,  
 f : 𝔽_q^k→𝔽_q^l and
𝐮↦𝐅𝐮; 𝐅∈𝔽_q^l × k
with k≥ q^l-1. If the number of distinct columns of 𝐅 is at least q^l-1, then all the cosets of 𝔽_q^k/ker(f) will have a unit vector. Then, the function distance matrix will be of the form 

    [𝐃_f(t,f_0, f_1 f_q^l-1)]_ij =
    	
    		
    		2t;   if i  j
    
    		0;      else,

 i.e, the diagonal entries are 0 and the non-diagonal entries are 2t.

So, the parity vectors satisfying the distance requirements will be an ECC of cardinality q^l and minimum distance 2t. Essentially we are reducing the dimension of the error correction problem from k ≥ q^l to l and minimum distance requirement from 2t+1 to 2t.




§ DISCUSSION

We proposed a lower bound for the redundancy required for a function-correcting code, which also led to a bound on the redundancy of classical ECCs when the function considered is a bijection. We explored a class of function-correcting codes where the function to be computed at the receiver is linear. We showed that the the adjacency matrix of 𝒢_f(t,k,r) has a recursive block circulant structure. When the domain of the function is a vector space over a field of characteristic 2, we characterised the spectrum of the adjacency matrix, which leads to lower bounds on redundancy. Functions that can attain this lower bound are yet to be found. For linear functions, we showed that the generalised Plotkin bound proposed in <cit.> simplifies for linear functions. We proposed a version of the sphere packing bound for coset-wise coding. We characterised a class of functions for which coset-wise coding is optimal and proposed a coding scheme for such functions. We also characterised a class of functions for which the redundancy to be added for coset-wise coding is equivalent to a lower dimensional classical ECC. Further research directions include using the the structure of 𝒢_f(t,k,r) to get improved bounds and coding schemes and to identify functions and coding schemes that can attain or come close to the proposed bounds. Linear codes for function correction are yet to be explored.





§ ACKNOWLEDGEMENT

This work was supported partly by the Science and Engineering Research Board (SERB) of Department of Science and Technology (DST), Government of India, through J. C. Bose National Fellowship to B. Sundar Rajan.

11
	FCC 
	A. Lenz, R. Bitar, A. Wachter-Zeh and E. Yaakobi, "Function-Correcting Codes," in IEEE Transactions on Information Theory, vol. 69, no. 9, pp. 5604-5618, Sept. 2023, doi: 10.1109/TIT.2023.3279768.
	
	pairwise read
	Qingfeng Xia, Hongwei Liu, Bocong Chen, "Function-Correcting Codes for Symbol-Pair Read Channels",	arXiv:2312.16271
	
	stinson
	 D. R. Stinson, "Combination Designs: Combinatorial Designs: Constructions and Analysis". Cham,
	Switzerland: Springer, 2003
	vizing Cartesian
	
	V.G. Vizing, Cartesian product of graphs, Vych Sis (Russian) 9, 30-43 (1963); In Computer Elements and
	Systems (English translation), Vol. l-9 pp. 352-365, Israel Program for Scientific Translation, Jerusalem,
	(1966). 
	product graphs
	P.K. Jha, G. Slutzki, Independence numbers of product graphs, Journal: Applied Mathematics Letters, : 1994, ISSN: 0893-9659
	cvetkovic
	D. M. Cvetkovic, M. Doob, and H. Sachs. "Spectra of graphs". Academic Press, New York, 1980.
	
	codetables
	M. Grassl, “Bounds on the minimum distance of linear codes and
	quantum codes,” available online at http://www.codetables.de
	




	




