High-throughput Hardware Architecture Design and Realization of RaptorQ Code Decoder

隨著科技越來越發達，智慧型手機可以提供的功能也越來越多，其中多媒體串流是普遍大眾經常使用到的ㄧ項服務；然而在此項服務中，傳遞延遲是影響視聽體驗最重要的影響因素。不幸的是，無線通訊常常會受到通道效應的影響，因此若沒有有效錯誤更正碼的協助，要提供ㄧ個可靠的無線通訊架構是幾乎不太可能的。傳統的無線通訊主要是透過重新傳送直到接收端成功地收到為止，以提供可靠的無線傳輸；然而湧泉碼的概念則是保留已成功收到的訊號，並繼續接收其他的編碼訊號直到足以成功解碼為止，此一概念在近年來吸引了大量的注意，而且也已應用在許多的環境設定中。 RaptorQ code是目前最新ㄧ代的湧泉碼，相較於之前的湧泉碼，RaptorQ code提供了更大的設計彈性以及更低的解碼失敗率，然而其解碼的架構亦相當複雜。傳統的RaptorQ code解碼器需要求得ㄧ個相當大矩陣的反矩陣，為了避免此ㄧ部分所需要的大量運算量，本論文改為事先求得ㄧ反矩陣，再根據遺失訊號所對應的列向量去對已知的反矩陣作修正，使得大部分的運算量皆移至離線狀態。另ㄧ方面，傳統演算法會先經由求得反矩陣的過程，同時得到中間訊號值，接著再利用中間訊號進而還原出來源訊號；然而新式演算法在此ㄧ部分利用事先求得傳送矩陣反矩陣的特性，將兩個步驟合併以進一步地化簡運算量。最後則是利用RaptorQ code的有系統特性，避免再次求得成功收到的來源訊號。 本論文所提出的新式解碼演算法不僅用軟體完成模擬，亦將其實現成硬體電路以及利用FPGA板驗證，以證明此一演算法的可行性。With advances in technology, there are much more services that a smartphone can provide. The multimedia streaming is the most common one that people use. However, transmission latency is of utmost important to quality of viewing/listening experiences. Unfortunately, wireless transmission often suffers channel fading that renders robust transmission almost impossible without effective error correction mechanism. Conventional protocol generally retransmits the erased coded sequence until the receiver receives it correctly. Fountain codes, on the other hand, keep the partially decoded information and continue to receive and decode the coded symbol until the whole information sequence can be recovered. Such rateless code has drawn a great deal of attention and has been applied in many scenarios. RaptorQ code is the latest generation of Raptor codes. Compared with the previous version, RaptorQ code provides higher flexibility and the lower decoding failure probability. However, the decoding procedure is also much more complicated. Conventionally, the decoding of RaptorQ codes requires inverting a huge matrix. Instead of such costly matrix inversion, we proposed to calculate the inverse of another matrix whose rows are a little different from the one that needs to be decoded. Therefore, most computations are shifted offline. Next, previous decoding usually decodes the intermediate symbols while inverting the matrix, and recovers the information sequence from the intermediate symbols. With the pre-calculated inverse, the proposed algorithm combines the intermediate sequence decoding and the procedure of information sequence recovery to reduce the complexity. Last, due to the systematic code property of the RaptorQ code, we proposed a new method that avoids many unnecessary computation when decoding the received information sequence. Finally, the proposed decoding algorithm is not only simulated on software, but also verified with FPGA board to prove its feasibility