# PLORC: A Pipelined Lossless Reference-Free Compression Architecture for FASTQ Files
## 3 Proposed Decompressor
### The Quality Decompressor Module  
#### 3.3.1 The Huffman Decoder Module  
The primary challenge in the Huffman decoding process is to extract Huffman codewords from the input. The Huffman encoding results are of two features:  
* Huffman code words are prefix codes, which means each code is not the prefix of the other codes.
* A 16-bit width is enough for Huffman code words because of the limited types of characters. These two features allow parallel comparisons between the Huffman decoding input and the Huffman Dictionary items to expedite processing. Two kinds of registers are generated from the Huffman dictionary:  
\begin{table}
\begin{tabular}{c c c} \hline _‘diff’_ & **0** & **1** \\ \hline How many bytes should be read & Read 1 byte when _‘sym_cnt’_ = 0; & Read 2 bytes when _‘sym_cnt’_ / = 0; \\  & otherwise read no byte. & otherwise read 1 byte. \\  & example: Steps (12) and (41). & Example: Steps (1), (14), and (43). \\ \hline The source of the output = _’c_base’_. & Output = _’temp’_. \\  & Example: Step (2)–(12), (15)–(41), and (44)–(45). & Example: Steps (13), (14), (42), and (43). \\ \hline How to update & _‘sym_cnt’_ = _‘temp’_; & (a) if one byte is read, _‘sym_cnt’_ = _‘sym_cnt’_-1; \\  _‘sym_cnt’_ and _‘temp’_ & then _‘temp’_ = new input. & _‘temp’_ = new input. \\  & after reading input bytes & Example: Steps (12) and (41). & (b) if two bytes are read, _‘sym_cnt’_ = the first byte, _‘temp’_ = the second byte. \\  & & Example for (a): Steps (13) and (42); \\  & & Example for (b): Step (1), (14), \\  & & and (43). \\ \hline \end{tabular}
\end{table}
Table 4: A classification of the operations in Figure 18.  
* _'code_times[i]'_: an 8-bit width register that specifies the number of Huffman code words with i-bit length.
* _'code_start[i]'_: the starting code for i-bit length Huffman code words. If no i-bit length Huffman code word exists, these registers hold a value of 0. For example, the _'code_times[i]'_ and _code_start[i]'_ generated from the Huffman code table in Figure 13 are listed in Table 5. The _'code_times[i]'_ values are in decimal format. The prefix '0x' means the _'code_start[i]'_ values are in hexadecimal format.  
Algorithm 1 outlines the comparison process. The Huffman decoding input is stored in a register named _'bytes'_. The _'diff[i]'_ values and the comparison processes can be performed concurrently in the FPGA implementation.  
```
1:for\(i\gets 1\), 16 do
2: diff[i] \(\leftarrow\) bytes[0:i-1] - code_start[i]
3:if\(0<=\) diff[i] \(<\) code_times[i] then
4: break;
5:endif
6:endfor
7: bytes[0:i-1] is a Huffman encoding result.
```  
**Algorithm 1** Finding the Huffman encoding result.  
Figure 19 shows an example of the Huffman decoding process, where _'start'_ represents where the Huffman code begins, and _'addr'_ means the start address of the Huffman encoding results. Algorithm 1 shows how to look up a symbol in the Huffman dictionary.  
Another [PERSON] decoding process example is listed in Table 6. The decoding input is '1001011100011001'. Only when i = 3, the condition in Algorithm 1 is satisfied. Therefore, '100' is identified as a valid Huffman code.  
Figure 19: An example of the [PERSON] decoding process.  
\begin{table}
\begin{tabular}{l c c c c c} \hline \hline
**i** & **code\_start[i]** & **code\_times[i]** & **i** & **code\_start[i]** & **code\_times[i]** \\  & **(hex)** & **(dec)** & & **(hex)** & **(dec)** \\ \hline
1 & 0x0 & 1 & 9 & 0x1f2 & 7 \\
2 & 0x0 & 0 & 10 & 0x3f2 & 13 \\
3 & 0x4 & 2 & 11 & 0x7 fe & 2 \\
4 & 0x0 & 0 & 12 & 0x0 & 0 \\
5 & 0x18 & 3 & 13 & 0x0 & 0 \\
6 & 0x36 & 4 & 14 & 0x0 & 0 \\
7 & 0x74 & 6 & 15 & 0x0 & 0 \\
8 & 0x74 & 5 & 16 & 0x0 & 0 \\ \hline \hline \end{tabular}
\end{table}
Table 5: The information generated from the Huffman code word length example.