# CoFi: Coding-Assisted File Distribution over a Wireless LAN
## 3 Coding Based Batching and Caching in CoFi
### Background: Randomized Network Coding  
Existing coding based wireless unicast protocols have mostly adopted the following batch based scheme, which was first introduced by [PERSON] et al. [26]. Before transmission, in order to facilitate the encoding of the original data file, it is grouped into batches (Figure 1), each containing \(n\) blocks of size \(k\) bytes. \(n\) and \(k\) are termed batch size and block size, respectively. A batch can be represented as a \(n\times k\) matrix \(B\), with rows being the n blocks, and columns the bytes (integers from 0 to 255) of each block. In each batch the coding operation is performed. The encoding operation produces a linear combination of the original blocks in this batch by \(X=R\cdot B\) (Figure 2), where \(R\) is a \(n\times n\) matrix composed of random coefficients in the Galois field \(GF(2^{8})\)[27]. The coding coefficients (rows in \(R\)), along with the coded blocks (rows in \(X\)), are packetized and transmitted to the receiver.  
Figure 1: Batch files for random linear encoding.  
Figure 2: The encoding operation is equivalent to a matrix multiplication \(X=R\cdot B\) (within the finite field \(GF\) (\(2^{8}\))), where \(R\) and \(B\) are the random coefficient matrixes, and \(B\) is the original data blocks in one batch. The decoding operation is the matrix reversion: \(B=R^{-1}\cdot X\).  
The decoding operation at the receiver side is the matrix reversion \(B=R^{-1}\cdot X\), where each row of \(X\) represents a coded block and each row of \(R\) represents the coding coefficients accomplished with it [27]. It is required that the matrix \(R\) is of full rank, i.e., the receiver must collect \(n\) independent coded blocks for this batch to successfully recover the original batch \(B\). Afterwards, it returns a single ACK packet to the sender, which confirms the successful decoding of the entire batch.  
Random linear network coding allows a re-encoding operation at the helper node. Specifically, it produces a new block by re-encoding existing blocks it has overheard in this batch. The re-encoding operation replaces the coding coefficients accomplished with the original coded packets with another set of random coefficients. For instance, if we consider the existing coded packets to be rows in the matrix \(Y\), which from the viewpoint of the AP was obtained using \(Y=R_{y}\cdot B\) (\(B\) is the original un-coded packets and \(R_{y}\) is the random coefficients), then the helper node may produce a new code block by re-encoding existing packets as \(Y^{\sim}=R^{\sim}\cdot R_{y}\cdot B=R_{y}^{\sim}\cdot B\). As a result, the original coefficients \(R_{y}\) are replaced by \(R_{y}^{\sim}\). The re-encoding operation circumvents the packet level scheduling problem in traditional MAC caching protocols [5; 6], because by randomly mixing information from all existing blocks, a newly generated coded block is innovative to the receiver with a probability close to 1 [17].  
Note that the packet overhead of network coding is negligible, since the size of the coding coefficient (\(n\)) is usually much smaller than the packet size (\(k\)). This issue has been well recognized in existing work [19].