SPRINGER BRIEFS IN
`
`Jafar A. Alzubi
`
`
`Forward Error
`
`ELECTRICAL AND COMPUTER ENGINEERING
`
`
`
`Correction Based
`On Algebraic-
`Geometric Theory
`
`CCCCC
`
`0000000000000
`
`Apple vs. Caltech
`IPR2017-00701
`Apple 1141
`
`

`

`SpringerBriefs in Electrical and Computer
`Engineering
`
`For further volumes:
`
`htipflwww .spl'ingencomfseriesf 10059
`
`

`

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

`

`Jafar A. Alzubi
`
`Thomas M. Chen
`
`School of Mathematics, Computer Science
`and Engineering
`City University London
`Northampton Square
`UK
`
`Faculty of Engineering
`Al—Balqa Applied University
`Al—Salt
`Jordan
`
`Omar A. Alzubi
`
`Prince Abdullah Ben Ghazi Faculty
`of Information and Technology
`Al-Balqa Applied University
`Al—Salt
`Jordan
`
`[SSN 219l—8112
`ISBN 9?8—3—319—08292—9
`D01 10. l00?f978—3—3 19—08293—6
`
`(electronic)
`ISSN 2191—8120
`ISBN 978—3—319—08293—6
`(eBook)
`
`Springer Cham Heidelberg New York Dordrecht London
`
`Library of Congress Control Number: 2014942050
`
`© The Authotts) 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 compuler 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 not 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 (wwwspringercom)
`
`

`

`T0 Fatima and Mira
`
`—Jafar A. Alzubi
`
`T0 Zulfah, Mariam, Ahmad and Yoasef
`
`form” A. Alzubi
`
`T0 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 ReedfiSolomon (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 codes is 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
`
`BER performance of AG codes and RS codes using 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 codes using
`quadrature amplitude modulation (loQAM and 64QAM) schemes are presented
`
`for the first time (to our knowledge) and shown to outperform RS codes at 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 performance is evaluated
`by simulations in Matlab, and results are presented for the first time in the liter—
`
`ature. They show significant performance improvements but at 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 AGwlBTCs are presented
`along with new simulation results. Again appearing for the first
`time in the
`
`vii
`
`

`

`viii
`
`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 PhD. 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
`
`\lONONUIJb-IBUJMH
`
`9 9
`
`10
`12
`
`13
`
`22
`23
`24
`
`25
`25
`26
`27
`27
`
`31
`31
`34
`36
`
`37
`37
`
`ix
`
`1
`
`Introduction ........................................
`
`1.1 Digital COmmunications Systems ......................
`
`1.1.1 Error Control Coding ..........................
`1.1.2 Block and Convolutional Codes ..................
`1.2 Motivations ......................................
`
`1.3 Aims and Objectives ...............................
`1.4 Original Contributions ..............................
`1.5 Book Layout .....................................
`References ..........................................
`
`2 Theoretical Background ................................
`
`2.1 Algebraic Geometric Codes ..........................
`2.1.1 Construction of AG Code Parameters ..............
`
`2.1.2 Designing AG Encoder ........................
`2.1.3 Designing AG Decoder ........................
`
`2.1.4 Complete Hard—Decision Decoding Algorithm for AG
`Codes Constructed From Hermitian Curves ..........
`2.2 Turbo Codes .....................................
`2.2.1
`Turbo Encoder ..............................
`
`Interleaver .................................
`2.2.2
`2.2.3 Turbo Decoder ..............................
`2.3 Block Turbo Codes ................................
`
`Summary .......................................
`2.4
`References ..........................................
`
`3 Literature Review ....................................
`
`3.1 Construction and Decoding of AG Codes .................
`
`Iterative Decoding of Block Turbo Codes .................
`3.2
`Irregular Iterative Decoding of Block Turbo Codes ..........
`3.3
`Summaly .......................................
`3.4
`References ..........................................
`
`

`

`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 ........................
`
`Summary .......................................
`4.4
`References ..........................................
`
`5
`
`Irregular Decoding of Algebraic-Geometric Block
`Turbo Codes ........................................
`
`5.1
`
`Irregular AG Block Turbo Code Encoder .................
`
`Irregular AG Non—binary Block Turbo Code Decoder ........
`5.2
`5.3 BER Performance of AG Irregular Block Turbo Codes
`Versus AG Block Turbo Codes ........................
`
`Summary .......................................
`5.4
`References ..........................................
`
`6 Conclusions .........................................
`
`6.1 Open Research Issues ...............................
`
`41
`41
`
`42
`
`45
`
`46
`
`54
`55
`
`57
`
`57
`
`62
`
`64
`
`6'."
`68
`
`69
`
`70
`
`

`

`Acronyms
`
`30
`
`Third Generation
`
`ADSL
`
`Asymmetric Digital Subscriber Line
`
`Algebraic Geometry
`AG
`Algebraic Geometric Block Turbo Code
`AG—BTC
`AG-IBTC Algebraic Geometric Irregular Block Turbo Code
`AWGN
`Additive White Gaussian Noise
`
`BCH
`BER
`
`BPSK
`BTC
`CTC
`
`DVB
`GF
`
`HIHO
`HSPA
`
`IBTC
`IDFT
`
`ITC
`LDPC
`LFSR
`LLR
`LR
`
`LTE
`MAP
`ML
`
`OFDMA
`PCCC
`PGZ
`
`QAM
`QPSK
`
`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
`Maximum a Posteriori
`Maximum Likelihood
`
`Orthogonal Frequency Division Multiple Access
`Parallel Concatenated Convolutional Code
`Peterson—Gorenstein—Zierler
`
`Quadrature Amplitude Modulation
`Quadrature Phase-Shift Keying
`
`

`

`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 {loT}
`consisting of interconnected common objects capable of sensing and processing
`may generate orders of magnitudes more data. At the same time, the amount of 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 oftransmission errors continues to- be a major research problem and practical
`
`concern for communications system designers [1].
`The basic principles ofdigital communication systems may be 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 lower limit on average bit rate for lossless source coding.
`Shannon’s noisy channel coding theorem described the maximum possible effi—
`ciency of error—correcting codes for a noisy channel. Channel capacity is the mutual
`information between the input and output of the channel maximized with respect to
`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 goal of efficient encoding and decoding methods to control errors due to
`the noisy channel. Modern communication systems are typically designed with error
`
`control as an essential part. Continual advances in 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.
`Springer—Briefs in Electrical and Computer Engineering,
`D01: 10. 1007;978-3-319-08293-6fl], © The Authods) 2014
`
`1
`
`

`

`2
`
`
`1
`
`Introduction
`
`
`
`
`
`
`Information Source —I- SourceEncoder % Channel Encoder
`
`
`
`
`
`
`
`
`Modulator
`
`
`Channel
`
`
`(Storage Medium)
`
`
`
`
`Noise
`
`
`
` Destination 4— 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
`diagram in Fig. 1.1 [l ]. Generally, the information source could be analog or discrete.
`An analog source is usually assumed to 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 known discrete alphabet.
`The source coder attempts to map the source symbols into bits as efficiently as
`possible, commonly by means of 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 more likely 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 produces a 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. Transmission is 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 into bits
`
`for the source decoder to recover the 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 media still has a very low bit error rate. The fiber
`
`acts as a waveguide for photons that is immune to external electromagnetic interfer~
`ence. The main causes ofsignal attenuation are light scattering and absorption within
`the fiber core. At the other extreme, radio channels are known to be one of the noisiest
`
`transmission media because they are vulnerable to several types ofimpairments 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 communication is 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 due to its simplicity and tractability.
`
`The AWGN channel is a good model for many satellite and deep space commu—
`nication links. It is not a good model for most terrestrial links because of multipath,
`terrain blocking, interference, and so on. However, for terrestrial path modeling,
`
`AWGN is commonly used to simulate background noise ofthe channel under study.
`
`1.1.1 Error Control Coding
`
`In the presence of a noisy channel, the channel encoder becomes necessary for error
`control. Channel coding adds redundant bits 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 body of theory has
`been developed with many techniques for error control coding [3]. Common tech-
`
`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 conupted
`codewords) into a binary or non-binary sequence called 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 sequence that is 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 research since it plays a crit—
`ical role in the performance of digital communication systems. Design of efficient
`channel decoders is 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 or fast as
`
`possible; the reproduced information at the channel decoder output should be reliable;
`
`and the implementation cost of the encoder and decoder should be reasonable [4].
`
`

`

`4
`
`|
`
`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 symbols in the current frame to produce its output as in block codes,
`or remembers a number of previous frames to produce its output as in the case of
`convolutional codes.
`
`A new type of channel codecs was introduced in [993 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 where a significant
`power saving is required or the operating signal-to-noise ratio (SNR) is very low.
`
`Deep space communications, mobile satellitefcellular communications, microwave
`links, and paging are some of 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 198]. These codes are constructed from
`algebraic curves (e.g., Hermitian curves, elliptic curves, hyperelliptic curves) over
`finite fields. One property of the AG codes is that they have relatively long size [6].
`One of the first and best known decoding algorithms for non-binary codes is the
`Berlekamp-Massey (BM) algorithm which proved to 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
`overcome this drawback, a new decoding algorithm essentially extending Berlekamp-
`
`Massey’s algorithm was introduced by Sakata in I988 [T]. 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 used in our design of the BTCs and 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 known construction
`method of AG codes presented by Justesen et al. is used in this book owing to its sim-
`plicity and versatility for different channel models. The constructed AG codes have
`
`shown significant improvements in BER performance in comparison to RS codes.
`This motivates us to use AG codes as code components of BTCs in the pursuit of
`further performance improvements.
`One important characteristic of AG codes is that they produce hard output. This
`does not fit 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 convening the one—pass system to an iterative
`system in order to improve the BER performance further.
`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 c0mplexity of the decoding process is an important trade-off with the
`performance. However, using AG codes along 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 a1 gebraic— 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-IBTCs is compared
`
`with the performance of the equivalent AG—BTC over different channel models and
`several modulation schemes.
`
`1.3 Aims and Objectives
`
`This book aims to 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 IBTCs are investigated. The BER performance of 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
`schemes over various practical channel models.
`The objectives of this book can be summarized as:
`
`0 Design and construct long AG codes and compare their BER performance with
`equivalent RS codes;
`1. Construct a new BTC by employing Chase-Pyndiah’s algorithm for extracting soft
`outputs frorn hard decision outputs using the AG codes as code Components;
`
`0 Evaluate the BER performance ofthe new AG-BTCs in comparison with RS-BTCs
`by means of computer simulations;
`
`0 Design and construct IBTCs using AG codes as code components in order to
`reduce the decoding complexity of AG-BTCs and enhance the BER performance
`as possible;
`
`0 Evaluate the BER performance of the new AG—IBTCs in comparison with
`equivalent AG—BTCs through computer simulations;
`1. Evaluate the above constructed codes over AWGN channels using several modu-
`lation schemes through computer simulations.
`
`

`

`6
`
`I
`
`Introduction
`
`1.4 Original Contributions
`
`In this book, AG codes are constructed using the simplified method of Justesen et al.
`from Hermitian curves over the 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 performance of the con-
`structed codes is evaluated in terms of BER over AWGN channel with binary phase—
`
`shift keying (BPSK) modulation scheme which matches the well known results in
`the literature. Moreover, the first simulation results showing the performance of AG
`codes over AWGN channel using quadrature phase-shift keying (QPSK), I6QAM
`and 64QAM modulation schemes are presented.
`In addition, an AG iterative 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 decoder based on Sakata’s algorithm). Simulation results show that AG—BTCs
`
`outperform the RS—BTCS in AWGN channels 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-lBTCs 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:
`
`a Chapter]:
`This chapter motivates the book, provides an overview, lists objectives and aims,
`and summarizes the key contributions of the work.
`
`0 Chapter2:
`This chapter presents the theoretical background covering AG code creation,
`encoding and decoding as well as fundamentals of TCs and BTCs.
`o Chapter3:
`This chapter reviews the literature on AG codes construction and decoding methods
`and the decoding of regular and irregular BTCs.
`:- Chapter4:
`
`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
`
`o ChapterS:
`This chapter introduces the developed IBTC with AG codes as code components.
`
`0 Chapter 6:
`This chapter finally discusses all the results achieved and draws conclusions with
`a discussion of possible future work.
`
`References
`
`Peer).—
`
`Lin S, 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):3?9-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.
`httpzr'i'www.loc.gov!catdin"enhancernentsi’fy0820100033l 04—i.himl
`Biglieri E (2005} Coding for wireless channels. Information technology-transmission, process-
`ing. and storage. Springer, Berlin. httpu'i'books.google.co.ukfbooks?id=seoU uxqu-oC
`. Sakata S (1988} Finding a minimal set of linear recurring relations capable of generating a
`given finite two-dimensional array. J Symbolic Comput 5(3): 321—337. doi:10.1016f3074'i-
`71?](88)8003 3-6. http:i’fwww.sciencedirectcomfscienceiarticlefpiii'SO7477”188800336
`
`

`

`Chapter 2
`Theoretical Background
`
`the theoretical background is presented covering design and
`In this chapter,
`construction of AG codes for the encoder and decoder along with important parame-
`ters. We also present a block diagram of the modified Sakata’s algorithm for the first
`time. It shows how the construction of AG codes using Hermitian codes is 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
`
`BTCs are 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, however fulfilling these properties
`by classical codes was not possible. In 1981, V. D. Goppa showed a way to 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
`AG codes though it is constructed from the affine points of a projective line not a
`projective curve which is the case of Goppa codes.
`
`The number of affine points determines the length of an AG code, so the cardinality
`ofthe chosen field restricts the length ofRS codes which result in relatively short code
`lengths. Replacing the projective line with a projective curve yields more affine points
`which means longer code lengths while keeping the same size of the finite field [2, 3].
`The longest possible codes can be obtained by choosing curves that have the
`maximum number of affine points which are called maximal curves, so the objective
`is always to find those curves whenever possible.
`
`A possible reason that AG codes have not been studied and investigated very well
`is that they require a good knowledge ofthe theory of algebraic geometry, a difficult
`
`J. A. Alzubi ct al., Forward Error Correction Based On Algebraic—Geometric Theory.
`Springer-Briefs in Electrical and Computer Engineering,
`D01: 10. 1007;“978-3-319-08293-642, © The Authods) 2014
`
`9
`
`

`

`10
`
`2 Theoretical Background
`
`and complicated branch of mathematics. To overcome the previously stated problem,
`a simplified construction method was introduced in 1989 by Justesen et a]. [4]. His
`
`method requires a basic understanding of algebraic geometry to produce AG codes.
`Although a limited number of AG codes—which is considered as a drawback—
`can be constructed using this method compared with using a more complicated AG
`approach, however this limited number of codes is still acceptable.
`
`2.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 over a finite field. Classes of
`
`good curves that could be used to produce good AG codes are the Hermitian curves,
`elliptic curves, hyperelliptic curves, and so on. as they all have one point at infinity.
`However, Hermitian curves with degree m = r + l where r = fl are well
`known from the previous classes of curves and most popular for constructing AG
`codes defined over a finite field Fq[4]:
`
`C(X, y) : xr+l + yr + y
`
`(2.1)
`
`To define the message length (k) and the designed minimum Hamming distance
`(d*), all affine points (the points causing the curve to vanish) as well as the point at
`infinity on the chosen curve must be found. The number of the affine points which
`satisfy C(x, y) = 0 is n = r3. Hasse-Weil bound gives an upper bound for the
`number of affine points a [4]:
`
`n52yfi+l+q
`
`(2.2)
`
`where y is the genus of the curve.
`It is worth giving a complete explanation of the curve genus as it is difficult to find
`a detailed simplified definition and method of genus computation. The genus is the
`
`maximum number of cuttings along non-intersecting simple curves [6]. The process
`of computing it is perhaps more interesting. Assume there exists a plane curve called
`C which is defined by f(x. 3‘) = 0 where f(x, 3!) is a two-dimensional polynomial
`composed of two variables. The degree of this polynomial is m which is the largest
`sum of the exponents ofx and y in each term of the curve equation. Then the genus
`of C is:
`
`1’
`
`_ (m —1)(m — 2)
`2
`
`(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 happens on
`the curve like a sharp corner (3‘2 = x3) or a crossing oftwo branches (y2 = x3 +x2).
`
`

`

`2.1 Algebraic Geometric Codes
`
`1 1
`
`Otherwise, when the curve has a finite number of 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 n0n-nega