THE DESIGN OF A VHDL BASED SYNTHESIS TOOL FOR BCH CODECS
A THESIS SUBMITTED TO
THE UNIVERSITY OF HUDDERSFIELD
IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF
MASTER OF PHILOSOPHY
By Ernest Jamro
School of Engineering,
The University of Huddersfield.
September 1997

 
 
 
 

Download
You can also download the text of my whole thesis, project files and examples od generated VHDL codes: (15, 11), (15, 7), (15, 5).

The thesis is in Word 6.0 format (each chapter separately) and compressed by the zip program into one file bch_thesis.zip.

Download thesis: bch_thesis.zip
Download project files: proj.zip
Download example of VHDL codes: examples.zip

Abstract

Bose, Chaudhuri and Hocquenghem (BCH) codes form a large class of powerful random error-correcting cyclic codes. BCH codes operate over algebraic structures called finite fields and there exist a multitude of decoding algorithms for these codes. Consequently designing BCH codecs is very involved and requires a high level of expertise. This thesis describes the design of the BCH codec synthesis (BCS) system. The BCS system is a design tool that automatically generates the VHDL description of a BCH code given the block length and error correcting ability of the code. These VHDL descriptions are then transported to the gate level using a proprietary synthesis tool. The BCS system is based upon the use of VHDL templates in conjunction with a high level C program. The VHDL templates contain basic knowledge of BCH encoders and decoders and are personalised by the insertion of data calculated by the C program. This data concerns the parameters of the code, the structures of the finite field arithmetic operators and the most appropriate decoding algorithm for the code being considered. Furthermore the C program generates commands files for simulation and a report file and carries out design optimisation.

In the course of this work four new arithmetic circuits operating over finite fields have been developed, a sum of products architecture, a dual-polynomial basis multiplier, a parallel polynomial basis multiplier and a circuit for raising field elements to the third power. These circuits are fast and hardware efficient and have been utilised in the BCS system.

In carrying out design optimisation, the BCS system employs extraction and algorithm selection. Accordingly, different decoding algorithms are used for single, double and triple or more error correcting BCH codes. Triple or more error correcting decoders may also be implemented in two different ways, depending on required hardware/decoding time trade-offs. By these means the developed BCH codecs are as hardware efficient as hand-crafted ones but are generated in a fraction of the time.

Contents
ABSTRACT II
ACKNOWLEDGEMENTS III
LIST OF FIGURES VII LIST OF TABLES VIII
GLOSSARY OF TERMS IX
1. INTRODUCTION 1
1.1 ERROR CODING 1
1.2.HARDWARE SOLUTIONS 3
1.3.VHDL AND SYNTHESIS 4
1.4 OVERVIEW OF THESIS 6
2. FINITE FIELDS AND FIELD OPERATORS 8
2.1 INTRODUCTION 8
2.1.1 Finite fields 8
2.2 FIELD DEFINITIONS AND BASIC FEATURES 8
2.2.1 The extension field GF(2m) 9
2.2.2 The polynomial basis and primitive elements 10
2.2.3 The Dual Basis 12
2.2.4 Normal basis 12
2.3 MULTIPLICATION BY A CONSTANT aJ 13
2.4 BIT-SERIAL MULTIPLICATION 14
2.4.1 Berlekamp multipliers 14
2.4.2 Massey-Omura Multiplier 16
2.4.3 Polynomial basis multipliers 17
2.4.3.1 Option L - LSB first 18
2.4.3.2 Option M - MSB first 19
2.4.4 Comparison of bit-serial multipliers 20
2.4.5 Generating the sum of products 22
2.4.6 Dual-Polynomial Basis Multipliers 24
2.4.7 Option A dual polynomial basis multipliers 25
2.4.7.1 Irreducible trinomials 25
2.4.7.2 Irreducible pentanomial 27
2.4.8 Dual polynomial basis multipliers option B 28
2.4.8.1 Irreducible trinomials 29
2.4.8.2 Primitive pentanomials 32
2.4.8.3 Summary of DPBM 33
2.5 BIT-PARALLEL MULTIPLICATION 35
2.5.1 Dual Basis Multipliers 35
2.5.2 Normal basis multipliers 36
2.5.3 Polynomial Basis Multipliers 36
2.5.4 Comparison of parallel multipliers 39
2.6 FINITE FIELD EXPONENTIATION 41
2.6.1 Squaring 41
2.6.2 Raising field elements to the third power 42
2.7 INVERSION 43
2.8 CONCLUSIONS 43
3. BCH CODES 45
3.1 BACKGROUND 45
3.2 BCH CODES 45
3.3 ENCODING BCH CODES 48
3.4 DECODING BCH CODES 49
3.4.1 Calculation of the syndromes 50
3.4.2 Solving the key equation 52
3.4.3 Finding the error locations 55
3.4.3.1 General case 55
3.4.3.2 Finding an error location for t = 2
56 3.5 REED-SOLOMON CODES 58
3.6 CONCLUSIONS 60
4. THE BCH CODEC SYNTHESIS SYSTEM 61
4.1 THE DESIGN APPROACH 61
4.2 DESIGN STRUCTURE 63
4.2.1 Overview 63
4.2.2 The C program 66
4.2.3 The Powerview Synthesis Tool (PVST) 67
4.3 THE ENCODER 67
4.4 THE DECODER 69
4.4.1 Single error correcting decoders 70
4.4.2 Double error correction decoders 70
4.4.3 Triple and more error correction decoders 71
4.4.3.1 The BMA with inversion 72
4.4.3.2 The inversionless BMA 76
4.5 CONTROL SYSTEM 77
4.6 THE BCS SYSTEM RESULTS 77
4.7 DESIGN OPTIMISATION 84
4.8 DESIGN SIMULATION 88
4.9 CONCLUSIONS 89
5.CONCLUSIONS AND SUGGESTIONS FOR FURTHER WORK 92
5.1 CONCLUSIONS 92
5.2 SUGGESTIONS FOR FUTURE WORK. 94
APPENDIX A THE LIST OF OPTIMAL IRREDUCIBLE POLYNOMIAL M<= 10 98
APPENDIX B POLYNOMIAL, DUAL AND NORMAL BASIS REPRESENTATIONS OF GF(24), GENERATED BY THE IRREDUCIBLE POLYNOMIAL P(X)= 1 + X + X4 99
APPENDIX C OPTIMAL DUAL BASIS TO POLYNOMIAL BASIS CONVERSIONS 100 APPENDIX D BCH CODES GENERATED BY PRIMITIVE ELEMENTS FOR M <=10 101
APPENDIX E ENCODER CONTROL SYSTEM - THE ILLUSTRATION HOW THE C PROGRAM, TEMPLATES AND VHDL FILES WORK TOGETHER. 103
APPENDIX F CONSTANT VALUES FILE: CONST.VHD 106
APPENDIX G THE (15,5) BCH CODE ENCODER 107
APPENDIX H CALCULATION OF THE SYNDROMES FOR THE (15, 5) BCH CODE. 109
APPENDIX I CHIEN SEARCH FOR THE (15,5) BCH CODE 111
APPENDIX J RAISING TO THE POWER THREE IN GF(25) WITH DESIGN OPTIMISATION. 113
APPENDIX K BIT-PARALLEL MULTIPLICATIONS 114
APPENDIX L FINITE FIELD INVERSION 116
APPENDIX M SINGLE ERROR CORRECTING DECODERS 117
APPENDIX N DOUBLE ERROR CORRECTING DECODERS 118
APPENDIX O TMEC DECODERS AND THE BMA WITH INVERSION 121
APPENDIX P TMEC DECODERS AND THE INVERSIONLESS BMA 125
APPENDIX Q THE DESIGN SIMULATION 128
REFERENCES 129
Glossary of terms
ARQ - Automatic Repeat Request
BCH - Bose-Chaudhuri-Hocquenghem
BCS - BCH Codecs Synthesis
DEC - Double Error-Correcting
DPBM - Dual Polynomial Basis Multiplier
DPBMA - Dual Polynomial Basis Multiplier option A
DPBMB - Dual Polynomial Basis Multiplier option B
ECAD - Electronic Computer Aided Design
FEC - Forward Error Correction
FPGA - Field Programmable Gate Array
GF - Galois Field GF(q) - The finite field containing q elements
LFSR - Linear Feedback Shift Register
LUT - Look Up Table
MPPBM - Mastrovito Bit-Parallel Polynomial Basis Multiplier
PDBM - Bit-Parallel Dual Basis Multiplier Pentanomial - Polynomial containing five non-zero coefficients
PLD - Programmable Logic Device
PMOM - Bit-Parallel Massey-Omura Multiplier
PPBM - Bit-Parallel Polynomial Basis Multiplier
PPBML - Bit-Parallel Polynomial Basis Multiplier option L
PPBMM - Bit-Parallel Polynomial Basis Multiplier option M
PVST - Powerview Synthesis Tool
ROM - Read Only Memory
RS - Reed Solomon
RTL - Register Transfer Level
SDBM - Bit-Serial Dual Basis Multiplier
SEC - Single Error-Correction
SPBM - Bit-Serial Polynomial Basis Multiplier
SPBML - Bit-Serial Polynomial Basis Multiplier option L
SPBMM - Bit-Serial Polynomial Basis Multiplier option M
TMEC -Triple and More Error-Correction
Trinomial - Polynomial containing three non-zero coefficients
VHDL - Very (High Speed Integrated Circuit) Hardware Description Language
VLSI - Very Large Scale Integration
Common variables and functions
f(x) - minimal polynomial
g(x) - generator polynomial H(pp) - Hamming weight of p(x)
k - number of information bits in a codeword
m - width of GF operations, n = 2m -1
n - length of a codeword
nk - number of check bits, nk= n-k
p(x) - irreducible polynomial in GF(2m) (see Appendix A)
t - number of symbols that can be corrected in a codeword

 

 
 
 
 
 

Go to Home Page for Ernest Jamro

For any questions or suggestions feel free to e-mail: jamro@uci.agh.edu.pl