FPGA üzerinde 5G uyumlu düşük yoğunluklu eşlik denetim kod çözücü gerçeklenmesi
Implementation of 5G compatible low density parity check decoder on FPGA
Yazar: BARIŞ BİLGİLİ
Danışman: PROF. DR. SIDDIKA BERNA ÖRS YALÇIN ; PROF. DR. ALİ EMRE PUSANE
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı / Elektronik Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2022
Konu: Elektrik ve Elektronik Mühendisliği = Electrical and Electronics Engineering
Dizin: FPGA = FPGA ; Hata düzeltme kodları = Error correction codes ; Kanal kodlama = Channel coding ; Sayısal elektronik = Digital electronic

Özet:
Günümüzde giderek artan sayısal veri üretimi ve veri ihtiyacı, bu verilerin iletilebilmesi için yüksek hızlı kablosuz haberleşme sistemlerini giderek daha önemli hale getirmektedir. Taşınan veri miktarının artması yeni gereksinimleri de beraberinde getirmektedir. Bunlardan ilki haberleşmenin daha hızlı yapılabilmesidir. İkincisi ise bu verilerin kanaldaki bozulmalardan etkilenmeden alıcı tarafa iletilebilmesidir. Haberleşme insanlar veya makineler arasında gerçekleşse de, hücresel ağlar veya uydu üzerinden sağlansa da yeni gereksinimler eklenebilmesine rağmen bu iki gereksinim değişmemektedir. Bu noktada üretilen standartlar belirtilen gereksinimleri karşılamaya çalışmaktadır. Hücresel haberleşme için güncel bir standart olan 5G'de ileri hata kodlama olarak Düşük Yoğunluklu Eşlik Denetim (Low Density Parity Check - LDPC) kodları veri kanallarındaki bu gereksinimleri karşılamak için önerilmiştir. Uydu haberleşmesinde ise İkinci Nesil Sayısal Video Yayını (Digital Video Broadcasting - DVB S2) gibi standartlarda LDPC kodları kullanılmaktadır.

LDPC kodları yapıları itibariyle esnek tasarım ve uygulamalara uygun kodlardır. Farklı blok boylarında ve paralel çalışmaya elverişli oldukları için Alanda Programlanabilir Kapı Dizileri (Field Programmable Gate Array - FPGA) ile gerçeklenmeleri avantajlı bir hale gelmektedir. LDPC kodları farklı kod çözme algoritmalarıyla çalışabildikleri için FPGA gerçeklemeleri yapılmadan önce bu algoritmalar performans ve gerçeklemeye uygunluk açısından incelenmelidir. Kod çözücünün düşük alan kullanımına ve yüksek veri hacmine sahip olması gerektiği için buna uygun bir algoritma seçilmelidir.

LDPC kodları genellikle bir eşlik denetim matrisi ile tanımlanırlar. Kod çözücü tasarımında bu matris, veri depolama birimlerinin boyutlarını ve bağlantıları belirler. Kod çözücüde algoritmanın çalıştığı asıl birim ise Denetim Düğümü Birimi ( Check Node Unit - CNU) olarak tanımlanır. Bu çalışmada 5G Yeni  Radyo (5G New Radio - 5G NR) standardı temel alındığı için veri boyutları ve bağlantıları büyük oranda belirlidir. Algoritma seçimi, paralelleştirme ve veri hacmini arttırma üzerine çalışmalar yapılmıştır. Donanım gerçeklemesi yapılırken karşılaşılan veri depolama, adresleme ve sıralama sorunlarına çözümler üretilmeye çalışılmıştır.

Döngüde FPGA (FPGA in the Loop - FIL), FPGA'de çalışması için bir donanım tanımlama diliyle (Hardware Description Language - HDL) yazılmış kodları MATLAB ortamı ile entegre ederek gerçek donanım üstünde çalışan kod ile yazılımdaki kodların beraber benzetiminin yapılması sağlayan doğrulama programıdır. HDL ile tasarım yaparken doğrulama yapmak çok önemli bir yer tutmaktadır ve FIL kullanılmadığı durumda herhangi bir bloğun doğrulamasını yapmak için test dosyaları oluşturup veri grupları hazırlayarak benzetim yapılması gerekmektedir. FIL sayesinde MATLAB ortamında oluşturulan veriler örnek modelle aynı anda gerçek donanım üzerinde çalışan HDL koduyla kıyaslanarak sonuçları doğrulanabilmektedir.

5G NR standardındaki LDPC matrisleri farklı boyutlara ve farklı satır ağırlıklarına sahip oldukları için bu çalışmada tasarlanan LDPC eşlik denetim biriminin farklı sayıda giriş ile çalışabilmesi gerekmektedir. Bu nedenle FIL kullanılarak farklı sayıda girişler için MATLAB ortamında doğrulama yapılmış ve FPGA üzerinde çalıştırılarak test edilmiştir.

Bu çalışmada hem FIL ile doğrulama yaparak tasarım ve doğrulama süreçlerinin hızlandırılması, hem de donanıma uygun algoritmalar seçilerek karmaşıklığı düşük ve veri hacmi yüksek bir eşlik denetim birimi tasarlanması, eşlik denetim biriminin çalışmasına örnek göstermek amacıyla 5G NR standardına uygun bir üst seviye tasarımının yapılması amaçlanmıştır.

Abstract:
Nowadays, the ever-increasing digital data production and data need make high-speed wireless communication systems more and more important in order to transmit these data. The increase in the amount of transmitted data brings new requirements with it. The first of these requirements is to increase the speed of communication. The second requirement is that the data is transmitted to the receiver without being affected by the channel noise. These two requirements do not change, although new requirements can be added whether communication takes place between humans or machines, or via cellular networks or satellite. At this point, standards are established to meet the specified requirements. In 5G, which is a current standard for cellular communication, Low Density Parity Check (LDPC) codes as forward error coding have been proposed to meet these requirements in data channels. These channels are Physical Uplink Shared Channel (PUSCH) and Physical Downlink Shared Channel (PDSCH). On the other hand, in satellite communication, there are LDPC codes in standards such as Digital Video Broadcasting Satellite Second Generation (DVB-S2).

LDPC codes are defined by parity check matrices and consist of two types of base units. These units are called bit nodes and check nodes. Each row in the parity check matrix represents a check node, and each column represents a bit node. The parity check matrix consists of ones and zeros. If the value at the intersection of any row and column is 1, it means that there is a connection between the intersecting bit node and the check node at this point. In the 5G NR standard, LDPC codes are defined with 2 base graphs. A large number of LDPC parity matrices are obtained from base graphs by expanding them with lifting sizes to support different block lengths.

LDPC codes, by their nature, are suitable for flexible design and applications. Since they are suitable for working in different block sizes and working in parallel, their implementation with Field Programmable Gate Arrays (FPGA) becomes advantageous. LDPC codes can work with different decoding algorithms, therefore these algorithms should be examined for performance and compatibility with implementation on FPGA before hardware design is made. Since the LDPC decoder should have low utilization and high throughput, an appropriate algorithm should be selected. Among the LDPC decoding algorithms, sum-product algorithm, min-sum algorithm, offset min-sum algorithm and attenuated min-sum algorithm come to the fore. The sum-product algorithm is also known as belief-propagation algorithm and is the default decoding algorithm in the literature. In all of these algorithms, the operation performed on the bit nodes is exactly the same, while the operation on the control nodes differs. Although the sum-product algorithm is the algorithm that gives the highest performance for LDPC codes, the use of the hyperbolic tangent function greatly increases both the computational complexity and the hardware implementation complexity. Therefore, hardware implementations given in the literature generally use the min-sum algorithm.

LDPC codes are usually defined by a parity check matrix. In the LDPC decoder design, this matrix determines the area of the data storage units and connections between the units in the design. The actual unit in the decoder where the algorithm runs is defined as the Check Node Unit (CNU). Since this study is based on the 5G New Radio standard, data sizes and connections are largely specific. Studies have been carried out on algorithm selection, parallelization and increasing the throughput. Solutions have been produced for data storage, addressing and scheduling problems encountered during hardware implementation. 

Input data of the LDPC decoder must be arranged in accordance with the matrix structure and stored in the RAMs. Taking advantage of the adjustable RAM widths, multiple messages can be stored and accessed together. In this way, high throughput can be achieved with parallel working CNU designs. As a solution, bit shuffling and circular shift methods have been proposed while accessing RAMs in studies in the literature. By using the bit shift values stored in the ROMs according to the connections in the matrix, the data stored together in the RAMs can be distributed to the bit node units and check node units in the correct order during a single read. While the processed data is writing back to the RAMs, it is written back to the correct addresses by reverse shuffling or reverse bit shifting with the same values stored in the ROM. Appropriate check node units and access sequences are suggested to avoid conflicts in RAM access while performing these read and write operations. The work of the check nodes should be sequenced, taking into account their latency. Conflicts occur when trying to access the same address to read in the next layer before the data is written to RAM after the previous layer has been processed. As a result of these conflicts, the data that has not been updated is transferred to the next layer and the results are overwritten in the same address in RAM. To avoid this situation, access sequences need to be regulated. Access sequences vary for different LDPC matrices and hardware implementations.

As a result of the studies on the literature, it has been decided that the most suitable structure to be implemented in hardware can be obtained by using the min-sum algorithm. This algorithm is suitable to be run on FPGA in terms of both having low complexity and being suitable for sequential access. For the design to be made with fixed points, keeping the messages 6 bit wide was found suitable as a result of the performance tests made on the min-sum algorithm model. Since the check node messages are collected at the bit nodes, the bit width is defined 2 bits more at the bit nodes.

CNU receives messages from the bit nodes and check nodes sequentially. Messages are indicated by the data valid signal. The end of the incoming message block is indicated by the end-of-block sign. When the CNU is ready to receive data on its input, it sends out a ready signal. A corresponding message output is sent to each of the bit node and check node messages coming to the CNU input. In this way, both the bit node and the control node can be updated simultaneously. In order for the updates between the layers in the LDPC matrix to take place without interruption, the CNU must be able to accept new data from the input while sending the valid data to the output. Otherwise, after updating the nodes of the previous layer, it is necessary to wait for all the inputs to be received and processed again in order to update the next layer. While the messages are given to the output, the new inputs received are processed in separate sequences, thus making the CNU operation uninterrupted.

FPGA in the Loop (FIL) is a validation program that integrates the codes written in a hardware description language (HDL) with the MATLAB environment to work in the FPGA, allowing the code running on the real hardware to be simulated together with the codes in the software. While designing with HDL, validation has a very important place and in case of not using FIL, it is necessary to simulate by creating test files and preparing data sets to validate any design block. By using the FIL, software model and HDL design running on hardware can be tested simultaneously by applying the data created in the MATLAB environment, and the results can be compared.

FIL can be used in different formats. By programming the FPGA via FIL with any HDL code, and sending the data from the MATLAB environment to the FPGA, the results can be observed and processed in the MATLAB environment. In this way, the processing time for big data can be shortened by taking advantage of the parallel operation feature of the FPGA. For validation and testing purposes, the model can be created in the MATLAB environment and run simultaneously with the HDL code on the FPGA, and the results of both the model and the hardware can be observed in the MATLAB environment. FIL was used for validation and testing purposes in this study.

Since the LDPC matrices in the 5G NR standard have different sizes and different row weights, CNU designed in this study should be able to work with different number of inputs. For this reason, verification was made in the MATLAB environment for different numbers of inputs using FIL and tested by running on FPGA.

In this study, it is aimed to accelerate the design and verification processes by verifying with FIL, and to design a low complexity and high throughput CNU by choosing algorithms suitable for the hardware, and to make a top-level design in accordance with the 5G NR standard in order to illustrate the operation of CNU. After the CNU design was validated with the FIL, a high-level architecture was designed for use within the LDPC Decoder. If all connections are to be processed at the same time, as many CNUs as the number of connections must be implemented on the FPGA. For this reason, the LDPC matrix was examined in a layered structure and each row was processed in serial layers. Reading and writing of each message in a layer is done serially. In order to provide high throughput, when a layer has finished all its readings, the next layer's readings are started without waiting for it to finish writing. When working in the order given in the 5G NR standard during the transitions between the layers, it is encountered that the next layer tries to reach the same address and sends the outdated data to the CNUs before the previous layer has updated the RAM yet. In this study, a different access order is proposed to resolve conflicts in RAM accesses. The order of access to addresses in reads within the layer does not affect the result. Based on this fact, the addresses are sorted in a unique way, preventing the outdated data from being read in the next layer.

Future studies will focus on error performance and try to implement more advanced algorithms such as offset min-sum and attenuated min-sum, which are built on the min-sum algorithm. Since these improvements will only be made on the CNU, they can be verified with the FIL and added to the LDPC decoder design without changing the top-level architecture. The development and validation environment created with FIL will be used by making customizations on the model.