Soft-decision decoding of moderate length binary cycle codes based on parity-check transformation
| dc.contributor.advisor | Versfeld, Daniel Jaco J. | en_ZA |
| dc.contributor.advisor | Ogundile, Olayinka O. | en_ZA |
| dc.contributor.author | Babalola, Oluwaseyi Paul | en_ZA |
| dc.contributor.other | Stellenbosch University. Faculty of Engineering. Dept. of Electrical and Electronic Engineering. | en_ZA |
| dc.date.accessioned | 2020-02-24T11:17:55Z | |
| dc.date.accessioned | 2020-04-28T12:09:58Z | |
| dc.date.available | 2020-02-24T11:17:55Z | |
| dc.date.available | 2020-04-28T12:09:58Z | |
| dc.date.issued | 2020-03 | |
| dc.description | Thesis (PhD)--Stellenbosch University, 2020. | en_ZA |
| dc.description.abstract | ENGLISH ABSTRACT: This thesis focuses on obtaining low complexity soft-decision (SD) decoding of binary cyclic codes with coding performance close to the optimal decoding algorithm. The belief propagation (BP) algorithm is commonly used to obtain near-optimal decoding but inappropriate for high-density parity-check (HDPC) codes. Therefore, alternative solutions such as the adaptive belief propagation (ABP) algorithm and the paritycheck transformation algorithm (PTA) have been proposed in the literature, based on matrix transformation, to effectively apply the BP decoding for HDPC codes. The extended parity-check transformation algorithm (EPTA) is introduced in this thesis to obtain a transformed parity-check matrix for the class of binary cyclic (BC) codes. The EPTA reduces the computational complexity of the known adaptive belief propagation (ABP) algorithm. However, it requires more iterative processes to attain comparable results to the ABP. Hence, a generalized parity-check transformation (GPT) algorithm for iterative SD decoding of the class of BC codes is developed. The proposed GPT algorithm is motivated by the EPTA and the belief propagation. The algorithm utilizes a new approach of matrix transformation to overcome the limitation with the BP algorithm for HDPC codes. The transformed matrix is obtained by permuting the columns of the initial parity-check matrix based on the reliability information received from the channel. Results show that the GPT offers a significant performance gain when compared with the hard decision Berlekamp-Massey (B-M) and belief propagation (BP) algorithms. It also produces a reasonable performance gain as compared with other iterative SD decoders. An important feature of the decoder is that it functions within a practical decoding time complexity and can be generally implemented for the class of linear block codes. Furthermore, a perfect knowledge model is developed to verify the optimality of all BP based algorithms for HDPC codes. The PKM computes a list of candidate matrices based on the prior knowledge of the transmitted codeword and it selects the best parity-check matrix according to a distance metric. The selected matrix is optimal since it minimizes the probability of error over various choices in the list. As a result, we show that for a given channel condition, the conventional transformed matrix, obtained by Gaussian reduction, is sub-optimal and will not necessarily contain unitary weighted columns at corresponding columns of the unreliable bits. Here, there exist specific scenarios where this matrix is not the same as the selected matrix from the PKM, giving room for improvement in the matrices of the BP in general. More so, the model can be used to verify performances of newly developed iterative SD decoders based on parity-check equations. In conclusion, the discovery of this thesis is important as it proposes a reduced computational time complexity soft-decision decoder for algebraic block codes. In view of some studies where the potentials of these coding techniques have been successfully demonstrated for cellular telephony, remote radio, spread spectrum communications, and satellite transmissions, the generalized parity-check matrix transformation algorithm can be implemented as a real-time decoder in order to reduce the number of transmission errors in digital communications. | en_ZA |
| dc.description.abstract | AFRIKAANSE OPSOMMING: Hierdie tesis fokus op die verkryging van lae-kompleksiteit sagte-besluit (SD) dekodering van binre sikliese kodes met koderingsprestasie naby die optimale dekodering salgoritme. Die geloof svermeerderingsalgoritme word algemeen gebruik om bynaoptimale dekodering te verkry, maar onvanpas vir HDPC-kodes met 'n ho digtheid. Daarom is alternatiewe oplossings soos die ABP-algoritme (adaptive belief propagation) en die pariteitstjek transformering salgoritme (PTA) in die literatuur voorgestel, gebaseer op matriks-transformasie, om die BP-dekodering effektief toe te pas vir HDPC-kodes. Die uitgebreide pariteitstjek transformering salgoritme (EPTA) word in hierdie tesis bekendgestel om 'n getransformeerde pariteitstjek matriks vir die klas binre sikliese (BC) kodes te verkry. Die EPTA verminder die berekeningskompleksiteit van die bekende algoritme vir adaptive belief propagation (ABP). Dit vereis egter meer iteratiewe prosesse om vergelykbare resultate met die ABP te bereik. Gevolglik word 'n veralgemeende algoritme vir pariteitstjek transformasie (GPT) vir iteratiewe SDdekodering van die klas BC-kodes ontwikkel. Die voorgestelde GPT-algoritme word gemotiveer deur die EPTA en die uitbreiding van geloof. Die algoritme gebruik 'n nuwe benadering van matriks-transformasie om die beperking met die BP-algoritme vir HDPC-kodes te oorkom. Die getransformeerde matriks word verkry deur die kolomme van die aanvanklike pariteitstjek matriks toe te laat, gebaseer op die betroubaarheidsinligting wat van die kanaal ontvang word. Resultate toon dat die GPT 'n beduidende prestasieverbetering bied in vergelyking met die harde besluit Berlekamp-Massey (B-M) en geloofs propagasie (BP) algoritmes. Dit lewer ook 'n redelike prestasieverbetering in vergelyking met ander iteratiewe SD-dekodeerders. 'N Belangrike kenmerk van die dekodeerder is dat dit binne 'n praktiese dekodering stydkompleksiteit funksioneer en in die algemeen gemplementeer kan word vir die klas linere blokkodes. Verder word 'n perfekte kennismodel ontwikkel om die optimaliteit van alle BPgebaseerde algoritmes vir HDPC-kodes te verifieer. Die PKM bereken 'n lys kandidaat matrikse op grond van die voorafkennis van die oordraagbare kodewoord en kies die beste matriks-toetsmatriks volgens 'n afstandmetriek. Die geselekteerde matriks is optimaal, aangesien dit die waarskynlikheid van foute as gevolg van verskillende keuses in die lys verminder. As gevolg hiervan, wys ons dat die konvensionele getransformeerde matriks, verkry deur Gaussiese reduksie, vir 'n gegewe kanaaltoestand sub-optimaal is en nie noodwendig eenheidsgeweegde kolomme by ooreenstemmende kolomme van die onbetroubare stukkies sal bevat nie. Hier bestaan spesifieke scenario's waar hierdie matriks nie dieselfde is as die geselekteerde matriks uit die PKM nie, wat ruimte gee vir verbetering in die matrikse van die BP in die algemeen. Meer nog, die model kan gebruik word om prestasies van nuut ontwikkelde iteratiewe SD-dekodeerders te verifieer gebaseer op pariteitstjek vergelykings. Ten slotte is die ontdekking van hierdie proefskrif belangrik, aangesien dit 'n verminderde berekeningstyd vir sagte besluitneming vir algebraese blokkodes voorstel. In die lig van enkele studies waar die potensiaal van hierdie koderingstegnieke suksesvol aangetoon is vir sellulre telefonie, afstandradio, verspreide spektrumkommunikasie en satellietuitsendings, kan die veralgemeende algoritme vir pariteitstjekmatriks transformasie as 'n intydse dekodeerder gemplementeer word om die aantal transmissiefoute in digitale kommunikasie te verminder. | af_ZA |
| dc.description.version | Doctoral | en_ZA |
| dc.format.extent | xvi, 98 leaves : illustrations | |
| dc.identifier.uri | http://hdl.handle.net/10019.1/107932 | |
| dc.language.iso | en | en_ZA |
| dc.publisher | Stellenbosch : Stellenbosch University | en_ZA |
| dc.rights.holder | Stellenbosch University | en_ZA |
| dc.subject | Parity check | en_ZA |
| dc.subject | Digital communication | en_ZA |
| dc.subject | Error-correcting codes (Information theory) | en_ZA |
| dc.subject | UCTD | en_ZA |
| dc.subject | Soft-decision decoding | en_ZA |
| dc.title | Soft-decision decoding of moderate length binary cycle codes based on parity-check transformation | en_ZA |
| dc.type | Thesis | en_ZA |