# PLORC: A Pipelined Lossless Reference-Free Compression Architecture for FASTQ Files
## 2 Proposed Compressor
### The Quality Compressor Module
#### 2.4.2 The Dictionary Generator Module  
The structure of the Dictionary Generator is shown in Figure 3. It transforms the Huffman code word length values into the corresponding Huffman code table. The code word length values are set by the users before the compression. The Huffman code table remains unchanged during the compression process.  
We introduce Canonical Huffman Coding (CHC) [37; 38; 39] to simplify the transmission of the Huffman dictionary. CHC allows generating binary Huffman codes \(f(i)\) from the Huffman code length \(i\) and several rules. These rules are listed below.  
* The codes with the same length are consecutive integers in binary format.  
\begin{table}
\begin{tabular}{c c c} \hline
**Input** & **Stack** & **Output** \\ \hline
1 & [0,1,2] & 1 \\
0 & [1,0,2] & 1 \\
2 & [0,1,2] & 2 \\
2 & [2,0,1] & 0 \\ \hline \end{tabular}
\end{table}
Table 2: An example of MTF encoding.  
Figure 12: The architecture of the MTF Encoder module.  
The first code \(f(i)\) of length \(i\) can be calculated from the last code of length \(i-1\), which can be expressed as \(f(i)=(f(i-1)+1)\times 2\).
* The first code with the smallest length starts from 0.
* If \(f(i+1)\) does not exist after \(f(i)\), and the nearest code word is \(f(i+k)\), then \(f(i+k)=(f(i)+1)\times 2^{k}\).  
The Dictionary Generator module consists of two submodules: the RLE Decoder module and the CHC Generator module.  
Since consecutive identical code length values occur frequently, the code length values are encoded as the _'code_bits'_ signal with the RLE method.  
The RLE Decoder module generates the code length \(i\) from the _'code_bits'_ signal. An example of the input and output of the RLE Decoder module is shown in Figure 13, where the total size of _'code_bits'_ is 9 bytes and the total size of \(i\) is 43 bytes. A smaller volume of the input saves time in configuring the Huffman encoder.  
The Fixed-Dictionary Huffman Encoder Module  
The traditional Huffman encoding consists of two phases: constructing a Huffman tree, and encoding based on the tree. This scheme requires the nodes on the tree to be scanned twice, which results in a longer encoding time [39]. The construction of a Huffman  
Figure 14: The architecture of the CHC Generator module.  
Figure 13: An example of the input and output of the RLE Decoder in the Dictionary Generator module.  
tree consumes 38% of the total encoding time [40]. In addition, the FPGA implementation of the Huffman tree construction process needs extra memory [41].  
To avoid the latency and resource overhead of constructing a Huffman tree, we omitted the Huffman tree construction process and utilized a fixed-dictionary Huffman encoder. Based on the observed character frequency distribution in Figure 10 and Table 3, applying fixed-dictionary Huffman encoding will lose little compression ratio. Additionally, this modification enables pipelined and resource-efficient implementation of the Huffman encoding process.  
The fixed-dictionary Huffman Encoder module consists of a RAM (Random Access Memory). The Huffman dictionary generated by the Dictionary Generator module is written in RAM. The Huffman encoding process is implemented by reading the RAM with the _'MTF output'_ signal as the reading address.