SPRINGER BRIEFS IN
`
`PETmaewalPAUe)
`Omar A. Alzubi
`
`RGRVee Aaaean
`
`
`
`Forward Error
`Correction Based
`On Algebraic-
`Geometric Theory
`
`
`
`al S)eyentae
`
`Ape
`vs.
`Caltec
`IPR2017-00701
`pl
`
`Apple vs. Caltech
`IPR2017-00701
`Apple 1141
`
`

`

`SpringerBriefs in Electrical and Computer
`Engineering
`
`For further volumes:
`
`http://www.springer.com/series/10059
`
`

`

`Jafar A. Alzubi -Omar A. Alzubi
`Thomas M. Chen
`
`Forward Error Correction
`Based On Algebraic-
`Geometric Theory
`
`gD) Springer
`
`

`

`Thomas M. Chen
`School of Mathematics, Computer Science
`and Engineering
`City University London
`Northampton Square
`UK
`
`Jafar A. Alzubi
`Faculty of Engineering
`Al-Balga Applied University
`Al-Salt
`Jordan
`
`Omar A. Alzubi
`Prince Abdullah Ben Ghazi Faculty
`of Information and Technology
`Al-Balqa Applied University
`Al-Salt
`Jordan
`
`ISSN 2191-8112
`ISBN 978-3-319-08292-9
`DOI 10.1007/978-3-319-08293-6
`Springer Cham Heidelberg New York Dordrecht London
`
`(electronic)
`ISSN 2191-8120
`ISBN 978-3-319-08293-6
`(eBook)
`
`Library of Congress Control Number: 2014942050
`
`© The Author(s) 2014
`This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of
`the material
`is concerned, specifically the rights of translation,
`reprinting, reuse of illustrations,
`recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or
`information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar
`methodology now known or hereafter developed. Exempted from this legal reservation are brief
`excerpts in connection with reviews or scholarly analysis or material supplied specifically for the
`purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the
`work. Duplication of this publication or parts thereof is permitted only under the provisions of
`the Copyright Law of the Publisher's location,
`in its current version, and permission for use must
`always be obtained from Springer. Permissions for use may be obtained through RightsLink at the
`Copyright Clearance Center. Violations are liable to prosecution under the respective Copyright Law.
`The use of general descriptive names, registered names,
`trademarks, service marks, etc.
`in this
`publication does not imply, even in the absence of a specific statement, that such names are exempt
`from the relevant protective laws and regulations and therefore free for general use.
`While the advice and information in this book are believed to be true and accurate at the date of
`publication, neither the authors nor the editors nor the publisher can accept any legal responsibility for
`any errors or omissions that may be made. The publisher makes no warranty, express or implied, with
`respect to the material contained herein.
`
`Printed on acid-free paper
`
`Springer is part of Springer Science+Business Media (www.springer.com)
`
`

`

`To Fatima and Mira
`
`—Jafar A. Alzubi
`
`To Zulfah, Mariam, Ahmad and Yousef
`
`—Omar A. Alzubi
`
`To Robin and Kayla
`
`—Thomas M. Chen
`
`

`

`Preface
`
`Algebraic-geometric (AG) codes are a new paradigm in coding theory which
`promise performance improvements for point-to-point communications systems.
`AG codes offer several advantages over state-of-the-art Reed-Solomon (RS)
`codes. First, their construction is based on selecting points on a curve creating a
`non-binary code with long code length and effective decoding. The bit error rate
`(BER) performance of AG codesis impressive and attractive for wireless networks
`with severe fading conditions. Second, AG codes are more flexible than RS codes
`because they are easily extendable to high finite fields with minimal additional
`complexity. Third, the decoding approach gets all required information from the
`received data without the need for a decoding list. It is very attractive from the
`perspectives of both reliability and buffering capacity. Finally, construction of AG
`codes from curves offers an endless supply of AG codes with different properties
`and parameters applicable for different applications.
`In this book, AG codes are designed, constructed and implemented from
`Hermitian curves. Simulations were carried out in Matlab to make comparisons of
`BERperformance of AG codes and RS codesusing different modulation schemes
`and various channel models such as additive white Gaussian noise (AWGN) and
`Rayleigh fast fading. Simulation results of BER performance for AG codesusing
`quadrature amplitude modulation (16QAM and 64QAM)schemesare presented
`for the first time (to our knowledge) and shown to outperform RS codesat various
`code rates. Results for the AWGN channel are presented in this book; results for
`the Rayleigh fast
`fading channel are contained in the first author’s Ph.D.
`dissertation.
`To further improve the BER performance, algebraic-geometric block turbo
`codes (AG-BTCs) are proposed and implemented in this book. Their design,
`construction and implementation are investigated. Their performanceis evaluated
`by simulations in Matlab, and results are presented for the first time in the liter-
`ature. They show significant performance improvements butat the expense of high
`system complexity due to the use of Chase-Pyndiah’s algorithm for AG codes.
`In order to reduce system complexity while maintaining high BER perfor-
`mance, this book proposes algebraic-geometric irregular block turbo codes (AG-
`IBTCs). The design, construction and implementation of AG-IBTCs are presented
`along with new simulation results. Again appearing for the first
`time in the
`
`vil
`
`

`

`vili
`
`Preface
`
`literature, results show that significant reduction in system complexity can be
`achieved while maintaining the high BER performance of AG-BTCs.
`This book is intended to be useful to researchers and students in digital com-
`munications. The reader is assumed to have an appropriate background in math-
`ematics and telecommunications. The presentation is intended to be self-contained
`with a substantial amount of background material included in the first half of the
`book. The second half concentrates on new research results. The advanced sections
`of the book may require a graduate level of education in communications.
`This book is a result of the Ph.D. work carried out by the first author at the
`College of Engineering in Swansea University, Wales. The authors are grateful to
`Dr. Martin Johnston at Newcastle University for his invaluable assistance at the
`early stages of the research. Special thanks are given to Dr. Martin Crossley in the
`Mathematics Department at Swansea University for mathematical assistance
`throughout this work.
`
`Salt, Jordan, April 2014
`London, UK
`
`Jafar A. Alzubi
`Omar A. Alzubi
`Thomas M. Chen
`
`

`

`Contents
`
`1
`
`Introduction ................. 0.02020 eee
`1.1 Digital Communications Systems ..................000.
`Lit Error Control Coding: ¢ 2.7 24.2 2.4 $2.5 PAG RR PRS
`1.1.2 Block and Convolutional Codes ...............020.
`1:2: Motivations: se: soy se6 2ay5 5 ee BES BE ROE EE EE EE BR
`1.3. Aims and Objectives .............. 0.00... 0000000005
`1.4 Original Contributions ............ 00.0.0... 000000000.
`133°)
`BOOK LAYOUtiscs sve cone caw ee ee eee
`RRELETENIGES 5
`&
`seuve Moe HR SR eee ee ee eee
`
`2 Theoretical Background......................2.02+-00 05
`2.1 Algebraic Geometric Codes ....................0.000.
`2.1.1 Construction of AG Code Parameters ..............
`21.2 Designing AG Encoder wc. sce cscs ace sowce gece ewe sees
`2.1.3. Designing AG Decoder....................00..
`2.1.4 Complete Hard-Decision Decoding Algorithm for AG
`Codes Constructed From Hermitian Curves ..........
`2.2 Turbo Codes.... 2... 0.0.00 00. eee
`221 Turbo Eneodeties says s wew wee see wee eee wee ee Se
`
`Interleaver... 2... 2. ee eee
`2.2.2
`22:5 Turbo Decoder << vag § vie #E.e PES PEG OES PEG HES ES
`2.3. Block Turbo Codes ............ 0.000000. 000000 0008,5
`2.4
`Summary ......... ccc eee ee ee ee ee ee eee
`References... 0... ene eens
`
`3 Literature Review ............... 0000 cece eee eee
`3.1 Construction and Decoding of AG Codes. ..............4.
`3.2
`Iterative Decoding of Block Turbo Codes.................
`3.3
`Irregular Iterative Decoding of Block Turbo Codes..........
`3.4
`Summary ..... 0... cee eee eee
`References; ces ex eeu eww gare ee eee eee
`
`NYADNDDNDUNFSSWNHRe
`
`10
`12
`
`13
`
`De,
`23
`24
`
`25
`25
`26
`27
`27
`
`31
`31
`34
`36
`
`37
`37
`
`

`

`x
`
`Contents
`
`4 Algebraic-Geometric Non-binary Block Turbo Codes ..........
`4.1. AG Non-binary Block Turbo Code Encoder...............
`4.2 AG Non-binary Block Turbo Code Decoder...............
`4.2.1
`Extracting Soft Information From the Hard Output
`of AG Decoder Using Chase-Pyndiah Algorithm ......
`4.3. BER Performance of AG Block Turbo Codes
`Versus RS Block Turbo Codes... ... 0.0... eee ee ees
`SUMMA ccs see wens ace eee e awee aire aoe au AOE RO; UE Mee
`4:4.
`References «
`: sac Sok Se ASE ASE FES EES OE EE SE EE EE Be
`
`5
`
`Irregular Decoding of Algebraic-Geometric Block
`Turbo Codes... 2.0.0... 0 ce eee
`5.1
`Irregular AG Block Turbo Code Encoder. ................
`5.2
`Irregular AG Non-binary Block Turbo Code Decoder ........
`5.3. BER Performance of AG Irregular Block Turbo Codes
`Versus AG Block Turbo Codes. .............0..0.0000.
`Summary es ces exe cow eer 4 eee Dew PRE EE ER ee ee wee
`5.4.
`References .. 2... 2.0 eee
`
`6 Conclusions............. 0.0.0 eee
`6.1 Open Research Issues..............0. 0.00000 00 002 eee
`
`41
`
`4]
`
`42
`
`45
`
`46
`54
`55
`
`57
`
`37
`62
`
`64
`67
`68
`
`69
`70
`
`

`

`Acronyms
`
`3G
`
`ADSL
`AG
`AG-BTC
`
`AG-IBTC
`AWGN
`
`BCH
`BER
`
`BPSK
`BTC
`crc
`DVB
`
`GF
`
`HIHO
`
`HSPA
`IBTC
`IDFT
`
`Third Generation
`Asymmetric Digital Subscriber Line
`Algebraic Geometry
`Algebraic Geometric Block Turbo Code
`Algebraic Geometric Irregular Block Turbo Code
`Additive White Gaussian Noise
`Bose—Chaudhuri—Hocquenghem
`Bit Error Rate
`Binary Phase Shift Keying
`Block Turbo Code
`Convolutional Turbo Code
`Digital Video Broadcasting
`Galois Field
`Hard Input Hard Output
`High Speed Packet Access
`Irregular Block Turbo Code
`Inverse Discrete Fourier Transform
`Irregular Turbo Code
`Low Density Parity Check
`Linear Feedback Shift Register
`Log-Likelihood Ratio
`Least Reliable
`Long-Term Evolution
`MAP
`MaximumaPosteriori
`ML
`Maximum Likelihood
`OFDMA
`Orthogonal Frequency Division Multiple Access
`PCCC
`Parallel Concatenated Convolutional Code
`PGZ
`Peterson—Gorenstein—Zierler
`Quadrature Amplitude Modulation
`QAM
`Quadrature Phase-Shift Keying
`QPSK
`
`ITC
`LDPC
`LFSR
`LLR
`LR
`LTE
`
`xi
`
`

`

`xii
`
`RSC
`SIHO
`
`SISO
`
`TPC
`VDSL
`WMAN
`
`Recursive Systematic Convolutional
`Soft Input Hard Output
`Soft Input Soft Output
`Turbo Product Code
`Very High Rate Digital Subscriber Line
`Wireless Metropolitan Area Network
`
`Acronyms
`
`

`

`Chapter 1
`Introduction
`
`In the past decade, the number of mobile devices has escalated driven mostly by
`demand for bandwidth-hungry smart phones. The need for efficient and reliable
`wireless communications has never been greater. The future Internet of Things (IoT)
`consisting of interconnected common objects capable of sensing and processing
`may generate orders of magnitudes more data. At the sametime, the amountof radio
`spectrum is essentially limited, motivating a perpetual search for efficient coding
`schemes. Although major advances have been realized in coding, wireless mobile
`systems remain highly susceptible to impairments in the radio channel, and the
`control of transmission errors continues to be a major research problemandpractical
`concern for communications system designers[1].
`Thebasic principlesofdigital communication systems maybe traced to Shannon’s
`historic 1948 paper establishing the foundations of information theory [2]. This
`chapter was concerned with the transmission of symbols from an information source
`to a destination through a noisy channel. Following a probabilistic view of the infor-
`mation source, Shannon’s source coding theorem established the concept of entropy
`as the lowerlimit on average bit rate for lossless source coding.
`Shannon’s noisy channel coding theorem described the maximum possible effi-
`ciency oferror-correcting codes for a noisy channel. Channel capacity is the mutual
`information between the input and output of the channel maximized with respectto
`the input distribution. If the source information is transmitted at a rate less than the
`channel capacity, then there exist codes that allow the probability of error at the des-
`tination to be arbitrarily small. In other words,it is theoretically possible to transmit
`information with very low error at a rate up to the channel capacity. Conversely, if
`the transmission rate is more than the channel capacity, it is not possible to achieve
`an arbitrarily small error probability.
`Since Shannon’s contribution,
`the research community has worked diligently
`towards the goalof efficient encoding and decoding methodsto control errors due to
`the noisy channel. Modern communication systemsare typically designed with error
`control as an essential part. Continual advancesin error control coding have led to
`more efficient and reliable digital communication systems.
`
`J. A. Alzubi et al., Forward Error Correction Based On Algebraic-Geometric Theory,
`SpringerBriefs in Electrical and Computer Engineering,
`DOI, 10.1007/978-3-319-08293-6_1, © The Author(s) 2014
`
`I
`
`

`

`2
`
`
`
`
`Information Source -}————-»_
`
`
`
`Source Encoder
`
`Channel Encoder
`
`1
`
`Introduction
`
`
`Modulator
`
`
`
` |
`
`
`
`eee
`
`
`Channel
`
`
`(Storage Medium)
`
`
`
`
` Destination
`
`
`
`
`h—,_ Source Decoder
`
`
`Fig. 1.1 A typical digital communication system
`
`Channel Decoder
`
`Demodulator
`
`
`1.1 Digital Communications Systems
`
`A classical view of a typical digital communication system is shown in the block
`diagramin Fig. 1.1 [1]. Generally, the information source could be analogordiscrete.
`An analog source is usually assumedto be converted into a discrete source through
`analog-to-digital conversion consisting of sampling and quantization. A discrete
`source can transmit a sequence of symbols chosen from a knowndiscrete alphabet.
`The source coder attempts to map the source symbols into bits as efficiently as
`possible, commonly by meansof variable length coding. The process is sometimes
`called data compression. The idea of variable length coding is to assign shorter
`codewords to symbols that are morelikely to be transmitted, and longer codewords
`to less likely symbols, thereby minimizing the average codeword length, e.g., by the
`well known Huffman code. The source coder producesa string of bits to the channel
`encoder.
`The channel encoder and modulator depend on the characteristics of the channel.
`It is possible to simply use modulation without a channel encoder. Transmissionis a
`physical process that is handled by the modulator. Without the channel encoder, the
`modulator converts bits from the source coder to baseband waveforms. If the channel
`
`is noiseless, the demodulator would convert the baseband waveforms back intobits
`for the source decoderto recoverthe transmitted symbols.
`Unfortunately, there is no perfect (error-free) channel in actuality, and different
`types of media have different characteristics. Even optical fiber which is well known
`to be one of the best transmission mediastill has a very low bit error rate. The fiber
`acts as a waveguide for photonsthat is immuneto external electromagnetic interfer-
`ence. The main causesofsignal attenuation are light scattering and absorption within
`the fiber core. At the other extreme, radio channels are knownto be oneofthenoisiest
`transmission media because they are vulnerable to several types of impairments such
`as reflections from objects (buildings, earth, atmospheric layers), diffraction (sec-
`ondary waves bending around sharp obstructions), scattering, diffusion, attenuation,
`
`

`

`1.1 Digital Communications Systems
`
`3
`
`and multipaths (radio signals taking different paths to the receiver). In addition, the
`source and destination may be mobile and moving.
`A critical part of communication system design is mathematical characterization
`of the channel. A common mathematical model is additive white Gaussian noise
`(AWGN)in which the impairment to communicationis a linear addition of wideband
`or white noise with a constant spectral density (expressed as watts per hertz of
`bandwidth) and a Gaussian distribution of amplitude. The model does not account
`for fading, frequency selectivity, interference, nonlinearity or dispersion. However,
`it is popular dueto its simplicity and tractability.
`The AWGNchannelis a good model for many satellite and deep space commu-
`nicationlinks. It is not a good model for mostterrestrial links because of multipath,
`terrain blocking, interference, and so on. However, for terrestrial path modeling,
`AWGNis commonly used to simulate background noise of the channel understudy.
`
`1.1.1 Error Control Coding
`
`In the presence of a noisy channel, the channel encoder becomes necessary for error
`control. Channel coding adds redundantbits after source coding to compensate for
`possible bit errors due to the imperfect channel. The channel encoder transforms the
`information sequence from the source encoder into a coded sequence of codewords.
`Codewords can be a binary or non-binary sequence. An enormous bodyoftheory has
`been developed with many techniques for error control coding [3]. Commontech-
`niques include parity bits, cyclic redundancy checks (CRC), block codes (including
`Hamming, Reed-Solomon, Golay, BCH), and convolutional codes.
`The channel decoder transforms the received sequence (of possibly corrupted
`codewords) into a binary or non-binary sequencecalled the estimated information
`sequence. The two main factors affecting decoding strategies are: the rules used in
`the channel encoding process and the noise characteristics of the channel(or storage
`medium).
`A perfect channel encoding and decoding system will produce an estimated infor-
`mation sequencethatis identical to the original information sequence, even though
`a number of decoding errors may introduced by the channel noise. The design and
`implementation of channel decoders is a major area of researchsinceit playsa crit-
`ical role in the performance of digital communication systems. Design of efficient
`channel decodersis an important topic in this book as well.
`Design is governed by these considerations: the probability of decoding errors
`should be minimized; the transmission of information should be dense orfast as
`possible; the reproduced informationat the channel decoderoutput should be reliable;
`and the implementation cost of the encoder and decoder should be reasonable [4].
`
`

`

`4
`
`1
`
`Introduction
`
`1.1.2 Block and Convolutional Codes
`
`Error control codes are divided structurally into two types: block codes and convo-
`lutional codes. The main difference between the two types is whether the encoder
`uses only the symbolsin the current frame to produceits output as in block codes,
`or remembers a numberofprevious frames to produce its output as in the case of
`convolutional codes.
`A newtype of channel codecs wasintroduced in 1993 by Claude Berrou and Alain
`Glavieux called turbo codes (TCs) and block turbo codes (BTCs) which proved to be
`very powerful error correction techniques that outperformed all previously known
`coding schemes. They can be used in any communication system wherea significant
`powersaving is required or the operating signal-to-noise ratio (SNR) is very low.
`Deep space communications, mobile satellite/cellular communications, microwave
`links, and paging are someof the possible applications of this coding technique. The
`idea behind TCs can be thought of as a refinement of the concatenated encoding
`structure plus an iterative algorithm for decoding the associated code sequence [5].
`A new family of non-binary block codes called algebraic-geometric (AG) codes
`were first introduced by V. D. Goppa in 1981. These codes are constructed from
`algebraic curves (e.g., Hermitian curves, elliptic curves, hyperelliptic curves) over
`finite fields. One property of the AG codesis that they have relatively long size[6].
`Oneofthe first and best known decoding algorithms for non-binary codesis the
`Berlekamp-Massey (BM) algorithm whichprovedto be very effective for short codes.
`However, because the decoding process involves two matrix inversions,the algorithm
`suffers from high complexity when dealing with long codes such as AG codes. To
`overcomethis drawback, a new decodingalgorithm essentially extending Berlekamp-
`Massey’s algorithm wasintroduced by Sakata in 1988 [7]. Sakata replaced the matrix
`inversion processes by generating a set of polynomials whose coefficients formed
`recursive relationships among an array of finite field elements. Sakata’s algorithm
`has been usedin our design of the BTCsand the irregular BTCs.
`
`1.2 Motivations
`
`The motivation of this book is to investigate the construction, decoding, implemen-
`tation, and BER performance evaluation of AG codes. A well knownconstruction
`method of AG codes presented by Justesenetal. is used in this book owingto its sim-
`plicity and versatility for different channel models. The constructed AG codes have
`shownsignificant improvements in BER performance in comparison to RS codes.
`This motivates us to use AG codes as code components of BTCsin the pursuit of
`further performance improvements.
`One important characteristic of AG codesis that they produce hard output. This
`does notfit well with the concept of BTCs where a soft output is usually required.
`This motivates us to consider Chase-Pyndiah’s approach for extracting soft output
`
`

`

`1.2 Motivations
`
`5
`
`from hard decision output and then converting the one-pass system to an iterative
`system in order to improve the BER performancefurther.
`Reed-Solomon block turbo codes (RS-BTCs) have been used as a reference to
`measure the gain in BER performance of AG-BTCs.In addition to the BER perfor-
`mance, the complexity of the decoding process is an important trade-off with the
`performance. However, using AG codesalong with Chase-Pyndiah’s algorithm may
`lead to an increase in the decoding complexity for better performance.
`In order to reduce the decoding complexity of the resultant system and con-
`sider practical implementation, we design algebraic-geometric block turbo codes
`(AG-BTCs) by constructing suitable algebraic-geometric irregular block turbo codes
`(AG-IBTCs). The construction, decoding and implementation of the new IBTC are
`investigated here. The performance of the new constructed AG-IBTCsis compared
`with the performance of the equivalent AG-BTC overdifferent channel models and
`several modulation schemes.
`
`1.3 Aims and Objectives
`
`This book aimsto design, construct and implement a reliable communications system
`with relatively low complexity compared to state-of-the-art systems. The design,
`construction and implementation of AG codes for use as code components in BTCs
`and IBTCsare investigated. The BER performanceof various AG codes are compared
`with the equivalent Reed-Solomon (RS) variations of BTC by means of computer
`simulations. Comparison results are presented for several code rates and modulation
`schemesover various practical channel models.
`The objectives of this book can be summarized as:
`
`e Design and construct long AG codes and compare their BER performance with
`equivalent RS codes;
`Construct a new BTC by employing Chase-Pyndiah’s algorithm for extracting soft
`outputs from hard decision outputs using the AG codes as code components;
`Evaluate the BER performanceof the new AG-BTCsin comparison with RS-BTCs
`by means of computersimulations;
`Design and construct IBTCs using AG codes as code components in order to
`reduce the decoding complexity of AG-BTCsand enhance the BER performance
`as possible;
`Evaluate the BER performance of the new AG-IBTCs in comparison with
`equivalent AG-BTCs through computer simulations;
`Evaluate the above constructed codes over AWGNchannels using several modu-
`lation schemesthrough computer simulations.
`
`

`

`6
`
`1
`
`Introduction
`
`1.4 Original Contributions
`
`In this book, AG codesare constructed using the simplified method of Justesenet al.
`from Hermitian curves overthe finite field GF (24) with varying code rates. The
`extension of BM decoding algorithm presented by Sakata is used with a majority
`voting (MV) technique to decode the produced codes. The performanceof the con-
`structed codes is evaluated in terms of BER over AWGNchannelwith binary phase-
`shift keying (BPSK) modulation scheme which matches the well knownresults in
`the literature. Moreover, the first simulation results showing the performance of AG
`codes over AWGNchannel using quadrature phase-shift keying (QPSK), 16QAM
`and 64QAM modulation schemesare presented.
`In addition, an AGiterative decoding technique is developed for non-binary BTCs
`constructed from AG codes as code components. Iterative decoding is applied to
`AG codes in order to enhance performance. This is done with the use of Chase-
`Pyndiah’s decoding algorithm for extracting soft output from a hard decision output
`(AG decoderbased on Sakata’s algorithm). Simulation results show that AG-BTCs
`outperform the RS-BTCs in AWGNchannels over the above mentioned modulation
`schemes.
`In order to reduce system complexity, AG-IBTCs are proposed, designed, and
`constructed. Measurements of the BER performance of the designed AG-IBTCs
`show that they perform no worse than the regular AG-BTCs and frequently better
`especially at higher order modulation schemes. Moreover, the AG-IBTCs system’s
`complexity is always reduced significantly compared to the complexity of AG-BTCs.
`
`1.5 Book Layout
`
`This book is organized into five chapters as follows:
`
`e Chapter |:
`This chapter motivates the book, provides an overview,lists objectives and aims,
`and summarizes the key contributions of the work.
`e Chapter2:
`This chapter presents the theoretical background covering AG code creation,
`encoding and decoding as well as fundamentals of TCs and BTCs.
`e Chapter3:
`This chapter reviewsthe literature on AG codes construction and decoding methods
`and the decoding of regular and irregular BTCs.
`e Chapter 4:
`This chapter extends the AG codes design into BTCs design by using the AG
`codes as code components of BTCs and shows AG codes construction using
`Justesen’s simplified method. Also the AG iterative decoding technique using
`Chase-Pyndiah’s algorithm is presented in this chapter.
`
`

`

`1.5 Book Layout
`
`7
`
`e Chapter5:
`This chapter introduces the developed IBTC with AG codes as code components.
`e Chapter6:
`This chapterfinally discussesall the results achieved and draws conclusions with
`a discussion of possible future work.
`
`References
`
`Pah Lin §, Costello DJ (2004) Error control coding, 2nd edn. Prentice-Hall, Upper Saddle River
`
`Shannon CE (1948) A mathematical theory of communication. Bell Syst Tech J 27(3):379-423
`Peter-Sweeney P (2004) Error control coding: from theory to practice. Wiley, New York
`Sklar B (1988) Digital communications: fundamentals and applications. Prentice-Hall, Upper
`Saddle River
`
`Vucetic B, Yuan J (2000) Turbo codes: principles and applications. Kluwer Academic, Boston.
`http://www.loc.gov/catdir/enhancements/fy0820/00033 104-t.html
`Biglieri E (2005) Coding for wireless channels, Information technology-transmission, process-
`ing, and storage. Springer, Berlin. http://books.google.co.uk/books?id=seoUuxiqG-oC
`Sakata S (1988) Finding a minimal set of linear recurring relations capable of generating a
`given finite two-dimensional array. J Symbalic Comput 5(3): 321-337. doi:10.1016/S0747-
`7171(88)80033-6. http://www.sciencedirect.com/science/article/pii/S0747717 188800336
`
`

`

`Chapter 2
`Theoretical Background
`
`the theoretical background is presented covering design and
`In this chapter,
`construction of AG codesfor the encoder and decoderalong with important parame-
`ters. We also present a block diagram of the modified Sakata’s algorithm forthefirst
`time.It shows howthe construction of AG codes using Hermitian codesis performed
`using a hard-input hard-output (HIHO) decoding algorithm. Fundamentals of TCs
`encoder, decoder and interleaver design are shown. Examples of the construction of
`BTCsare also presented.
`
`2.1 Algebraic Geometric Codes
`
`For a long time researchers attempted to realize a very long non-binary block code
`with high code rate and large Hamming distance, howeverfulfilling these properties
`by classical codes wasnotpossible. In 1981, V. D. Goppa showed a wayto construct
`these codes which are now called Goppa codes or AG codes[1]. Goppa explained the
`construction from affine points of an irreducible projective curve and a set of rational
`functions defined on that curve. The famous Reed-Solomon (RS) code represents
`the best and for most the simplest example that demonstrates the construction of
`AGcodes thoughit is constructed from the affine points of a projective line not a
`projective curve whichis the case of Goppa codes.
`The numberofaffine points determines the length of an AG code,so the cardinality
`ofthe chosenfield restricts the length of RS codes whichresult in relatively short code
`lengths. Replacing the projective line with a projective curve yields moreaffine points
`which meanslonger code lengths while keeping the samesizeofthe finite field [2, 3].
`The longest possible codes can be obtained by choosing curves that have the
`maximum numberofaffine points which are called maximalcurves,so the objective
`is alwaysto find those curves wheneverpossible.
`A possible reason that AG codes have not been studied and investigated very well
`is that they require a good knowledgeofthe theory of algebraic geometry,a difficult
`
`J. A. Alzubi et al., Forward Error Correction Based On Algebraic-Geometric Theory,
`SpringerBriefs in Electrical and Computer Engineering,
`DOI, 10.1007/978-3-319-08293-6_2, © The Author(s) 2014
`
`9
`
`

`

`10
`
`2 Theoretical Background
`
`and complicated branch of mathematics. To overcomethe previously stated problem,
`a simplified construction method was introduced in 1989 by Justesenetal. [4]. His
`method requires a basic understanding of algebraic geometry to produce AG codes.
`Although a limited number of AG codes—whichis considered as a drawback—
`can be constructed using this method compared with using a more complicated AG
`approach, howeverthis limited numberof codesis still acceptable.
`
`2.1.1 Construction ofAG Code Parameters
`
`According to Carrasco [5], an AG code can be constructed using Justesen’s simplified
`method by choosing an irreducible affine smooth curve overa finite field. Classes of
`good curvesthat could be used to produce good AG codesare the Hermitian curves,
`elliptic curves, hyperelliptic curves, and so on, as they all have one pointatinfinity.
`However, Hermitian curves with degree m = r + 1 where r = ,/@ are well
`known from the previous classes of curves and most popular for constructing AG
`codesdefinedovera finite field F, [4]:
`
`Cw, y) = xitl fh y" 4 y
`
`(2.1)
`
`To define the message length (k) and the designed minimum Hammingdistance
`(d*), all affine points (the points causing the curve to vanish) as well as the pointat
`infinity on the chosen curve must be found. The numberofthe affine points which
`satisfy C(x, y) = 0 is n = r°. Hasse-Weil bound gives an upper bound forthe
`numberofaffine points n [4]:
`
`n<2y/q+til+q
`
`(22)
`
`where y is the genus of the curve.
`It is worth giving a complete explanation ofthe curve genusasit is difficult to find
`a detailed simplified definition and methad of genus computation. The genusis the
`maximum numberofcuttings along non-intersecting simple curves [6]. The process
`of computing it is perhaps more interesting. Assumethere exists a plane curve called
`C whichis defined by f(x, y) = 0 where f(x, y) is a two-dimensional polynomial
`composedof two variables. The degree ofthis polynomial is m whichis the largest
`sum of the exponents of x and yin each term of the curve equation. Then the genus
`of C is:
`
`_ (m — 1)(m — 2)
`5
`
`(2.3)
`
`if and only if C is non-singular curve.
`A nonsingular curve, also called smooth curve, is the one which has no singular
`points. A singular point is defined as the point where something unusual happenson
`the curve like a sharp corner (y? = x3) or a crossing of two branches (y? =x3 4x7),
`
`

`

`2.1 Algebraic Geometric Codes
`
`ll
`
`Otherwise, when the curve hasa finite numberof singular points, it is called a singular
`curve [7].
`As Hermitian curves saturate the Hasse-Weil bound, they called maximal curves
`making them suitable to generate long AG codes. Justesen’s construction method
`suggests a non-negative integer j which is boundedby[8]:
`
`m—-2<j<
`
`
`
` |
`
`(2.4)
`
`Goppa or AG codesare of two types: functional Goppa codes (C;,) and residue
`Goppa codes (Cg). Thelatter is the dual of the former.In both types, the block length
`is equal to the numberofaffine points on the curve (n) [5]. To compute the length of
`the message for an AG code,a set ofrational functions with a pole of order equal or
`less than the degree of the divisor (a) at t