The Development of
Error-Correcting Codes
Chair Prof. Trieu-Kien Truong
IEEE Fellow, and Editor, IEEE Transactions
on Communications
Department of Information Engineering, I-Shou University,
Kaohsiung County, Taiwan, 840, R.O.C.
Education:
Ph.D.,University of Southern California, Los Angeles,
CA., January, 1976.
M.S.E.E., Washington University, St. Louis, Missouri,
June, 1971 .
B.S.E.E., National Cheng-Kung University, Taiwan,
June, 1967.
Major:
Data Compression, Error Correction Coding, Digital
Video Transmission, VLSI Architecture, Mathematics,
Digital Signal Processing and Multimedia.
Experience

I-Shou University



University of Southern California 1976-Aug. 1995



Department of Electrical Engineering, Communication
Science Institute.
Ultimate Scientific Applications Inc. 1993-Aug.,
1995
Jet Propulsion Laboratory (JPL) 1975-1992


Professor and Dean of College of Electrical and Sept.
1997-Present
Information Engineering Professor and Chairman of
Information Engineering Sept.1995-Present
Communications Systems Research Section.
Memorial Hospital Medical Center of Long Beach
1978-1985

Department of Radiology.
Professor Claude Elwood Shannon (April 30, 1916 – February 24, 2001)
The father of information theory
The Shannon limit:
C. E. Shannon, ”A Mathematical Theory of Communication,” Bell
Syst. Tech. J., pp. 379-423(Part 1); pp. 623-656(Part 2), July 1948.
Professor Irving Stoy Reed (born 1923 in Seattle,
Washington)
Professor Loo-Keng Hua (華羅庚)(November 12,1910- June 12,1985)
History(1)

The first people that Dr. Reed knew in coding other
than himself were David Muller and David Huffman.

David Muller and Dr. Reed were classmates at
Caltech. David Huffman and Dr. Reed met while on
the same ship in the U.S. Navy.

During the early 1940s none of them knew anything
about error-correcting codes; they had not yet been
discovered.
History of the Error-Correcting
Code(1/6)




In 1947, Dr. Hamming described the original idea of
the error-correcting codes first and constructed
Hamming code.
In 1948, the paper was published as The Bell
System Technical, titled, “Mathematical Theory of
Communication,” by C. E. Shannon.
In 1949, M. J. E. Golay published an article called
Notes on digital coding in the Proceedings of the
Institute of Electrical and Electronic Engineers. (23,
12) Golay code was described.
In 1954, Reed-Muller codes were described.
History of Reed-Muller
Codes(1/3)

In a notation of his own invention, Dr. Dave Muller
described a new error-correction code in his report
on logic design. His codes were based on what he
called a Boolean Net Function.

Dr. Reed decided what he must have had in mind
were what are called multinomials over a Boolean
field, the finite or Galois field GF(2) of two elements
0 and 1.
History of Reed-Muller
Codes(2/3)

From Professor Robert Dilworth at Caltech, Dr.
Reed had learned much about algebraic ring theory
and polynomial over fields.

His idea of using polynomials over the primitive finite
field GF(2) of two elements was very fruitful.
History of Reed-Muller
Codes(3/3)




By constraining the maximum degree of these
multinomials over N variables Dr. Reed managed to
construct an error-correcting code which was
equivalent to the codes Dr. Muller had found.
The algebraic structure imposed on these
multinomials made it possible for Dr. Reed to find a
decoding algorithm for these codes which is now
called majority-logic decoding. Also, Dr. Reed
demonstrated that these codes are group codes.
I. S. Reed, A class of multiple-error-correcting codes and the decoding
scheme,Technical Report No. 44, Lincoln Laboratory, M. I. T. (1953).
D. E. Muller, Metric properties of Boolean algebra and their applications to switching
circuits, Report No. 46, Digital Computer Laboratory, University of Illinois (1953).
History of the Error-Correcting
Code(2/6)





In 1957, cyclic codes were invented by Dr. Prange
at the Air Force Cambridge Research Center
(AFCRC).
In 1958, quadratic residue (QR) codes were
invented by Dr. Prange at the Air Force Cambridge
Research Center (AFCRC).
In 1959/1960, Dr. Alexis Hocquenghem, Dr. R. C
Bose, and Dr. D. K. Ray-Chaudhuri discovered
Bose–Chaudhuri–Hocquenghem (BCH) codes.
A. Hocquenghem, “Codes correcteurs d'erreurs,” Chiffres (Paris), 2:147–
156, September 1959.
R. C. Bose and Dr. D. K. Ray-Chaudhuri, “On a class of error-correcting
binary codes,” Information and control, 3, (1960), 68–79.
History of the Error-Correcting
Code(3/6)





In 1960, Reed-Solomon (RS) codes were invented
by Irving S. Reed and Gustave Solomon.
In 1967/1969, an efficient decoding algorithm
(Berlekamp Massey algorithm) for large-distance RS
codes was developed by Elwyn Berlekamp and
James Massey.
Irving S. Reed and Gustave Solomon,”Polynomial Codes over Certain Finite
Fields,“ Journal of the Society for Industrial and Applied Mathematics, 1960.
E.R.Berlekamp, Algebraic coding theory, McGraw-Hill, New York, 1968.
J.L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. on
Inform. Theory, vol. IT-15, January 1969.
History of the Error-Correcting
Code(4/6)

The BCH codes were given their present name by
W. Wesley Peterson in his “Error Correcting Codes”
published by John Wiley and Sons (1961).

Peterson also redefined them in a cyclic context to
complement his own work in algebraic decoding.

More coders and their codes owe their name and
fame to Peterson than anyone of whom we know.
History of the Error-Correcting
Code(5/6)

Perhaps it was the Galois field incorporation;
perhaps it was the nonbinary nature of the code; but
for years after its publication the Reed-Solomon
code was viewed as interesting mathematics and
little else.

It simply did not appear to be practical with the
computing capability of the day. Even in 1980s,
when people at JPL began to build and fly
spacecraft with error-correction coding, they turned
not to the Reed-Solomon code but to the more
straightforward but less powerful Reed-Muller
code.
History of the Error-Correcting
Code(6/6)

However, in the years since the late 1970s,
concurrent with the development of more powerful
computers and more efficient decoding architectures,
such as that of Berlekamp, the Reed-Solomon code
has been widely used in industrial and consumer
electronic devices.

At present billions of dollars in modern technology,
the compact disc memories, digital communications,
etc. depend on ideas that stem from the original
work of Solomon and myself almost 34 years ago.
Information
source
Source
encoder
Channel
encoder
Modulator
Channel
Destination
Source
decoder
Channel
decoder
Noise
Demodulator
Block diagram of a typical data
transmission or storage
without using the error-correcting code
Encode by using the RS code
Introduction to Algebra(1/3)

Finite field was invented by the early 19th
century mathematician, Evariste Galois.

Galois was a young French math whiz who
developed a theory of finite fields, now known as
Galois fields, before being killed in a duel at the
ripe "old" age of 21.

For well over 100 years mathematicians looked
upon Galois fields as elegant mathematics but of
no practical value.
Introduction to Algebra(2/3)

It was Dr. Reed’s idea to use the elements of
a finite field as an alphabet to use symbols
rather than bits, e.g., half-bytes or bytes for
the symbols.

This was the beginning of the thought
process that led ultimately to the ReedSolomon codes.
Introduction to Algebra(3/3)

Definition of a field (F, +, ×):





F is closed under “+” and “×”
“+” and “×” are associative
For all elements a and b in F, a+b=b+a. The
additive identity is denoted by 0. a+(-a)=0, -a is
the inverse with respect to addition.
For all nonzero elements a and b in F, a×b=b×a.
The multiplicative identity (unit element) is
denoted by 1. a× (a-1)=0, a-1 is the inverse with
respect to multiplication.
For any three elements a, b, and c in F,
a×(b+c)=a×b+a×c.
Construction of
m
Galois field GF(2 )

Consider m=3. Three representations for the
elements of GF(2m) generated by the primitive
polynomial p(x)=x3+x+1over GF(2):
Power
representation
Polynomial
representation
3-Tuple
representation
0
0
(0 0 0 )
1=α7
1
(1 0 0 )
α
α
α2
(0 1 0 )
α2
(0 0 1)
α3
1+α
(1 1 0)
α4
α+α2
(0 1 1)
α5
1+α+α2
(1 1 1)
α6
1
(1 0 1)
+α2
Types of Codes



Block codes: linear codes, cyclic codes,…
Convolutional codes
Random-like codes: turbo codes, LowDensity Parity-Check (LDPC) codes…
Linear black codes

(n, k) linear black codes: a message m of k bits is
encoded into a codeword c (code vector) with n bits.
 An (n, k) block code is said to be linear if the
vector sum of two codeswords is also a codeword.
 An (n, k) block code is spanned by k linearly
independent vectors, g0, g1,…,gk-1.
 The generator matrix G:
 g0 
g 
1 

G
, and c  mG
  


g k 1 
An example of linear black
codes-(6, 3) linear block code
Message
(a0, a1, a2)
(c0, c1, …, c5)
(0, 0, 0)
(0, 0, 0, 0, 0, 0)
(1, 0, 0)
(0, 1, 1, 1, 0, 0)
(0, 1, 0)
(1, 0, 1, 0, 1, 0)
(0, 0, 1)
(1, 1, 0, 0, 0, 1)
(1, 1, 0)
(1, 1, 0, 1, 1, 0)
(1, 0, 1)
(1, 0, 1, 1, 0, 1)
(0, 1, 1)
(0, 1, 1, 0, 1, 1)
(1, 1, 1)
(0, 0, 0, 1, 1, 1)
Codewords
 g0 
 g  0 1 1 1 0 0 
1 

G
 1 0 1 0 1 0
  

 1 1 0 0 0 1
g k 1 
m=(1, 1, 0)
 c= mG
=1(011100)+1(101010)+0(110001)
=(110110)

Cyclic codes

An (n, k) linear code C is called a cyclic code if any
cyclic shift of a codeword c is another codeword.
That is,
c =(c , c , …,c ) is a codeword in C, then
0
1
n-1
c’=(c , …c , c ) is also a codeword in C.
 The generator polynomial g(x) is with degree n-k. All
codewords can be represented as c(x)=m(x)g(x)
 The generator polynomial g(x) of (n, k) cyclic code is
a factor of xn-1.
1
n-1
0
(23, 12, 7) Goaly Code


(23, 12, 7) Golay code with minimum distance of 7 is
the only known multiple-error-correcting binary
perfect code.
Generator polynomial g1(x) or g2(x)


g1(x)=1+x2+x4+x5+x6+x10+x11
g2(x)=1+x+x5+x6+x7+x9+x11
Reed-Solomon Codes
Nonbinary cyclic codes with symbols belong to finite
field GF(2m)
 They are widely used in data communications and
storage systems for error control.
 A (n, k, d) RS code with the following parameters:
n=2m-1, n-k=2t, k=2m-1-2t, d =2t-1
 The generator polynomial g(x) of a t-error-correcting
RS code:

min
g ( x)  ( x   )( x   2 )  ( x   2t )
 g 0  g1 x   g 2t 1 x
2 t 1
x
where α is a primitive element in GF(2m)
2t
An example of the RS codes

Let m=8 and t =16. The RS code has the following
parameters:
 n=2m-1=255,
 n-k=2t=16,
 k=2m-1-2t=223,
 d =2t-1=33
(255, 223, 33) RS code is NASA standard code for
satellite and space communications.
min

Voyager 1 and 2
NASA photograph of one of the two identical
Voyager space probes Voyager 1 and
Voyager 2 launched in 1977
Deep Space Application of
Error-Correcting Code- Voyager
spacecraft
Uranus - Discrete Cloud
Uranus - Final Image
1996-11-26
1996-01-29
Ariel at Voyager
Closest Approach
2000-06-02
(n, k, d) Binary Quadratic Residue
(QR) Codes(1/6)

Binary quadratic residue (QR) codes are the most
powerful known cyclic codes. However, they are
very hard to decode.

Golay code is famously one of QR codes and is
extensively applied in error control system of
Voyager I and II.
(n, k, d) Binary Quadratic Residue
(QR) Codes(2/6)

Definition of quadratic residue
Let n  8t  1 be a prime number. The set Q of
quadratic residue modulo n is the set of nonzero
squares modulo n; that is,
Q  {i | i  j 2 mod n for 1  j  n  1}.
(n, k, d) Binary Quadratic Residue
(QR) Codes(3/6)

Definition of quadratic residue code
Let m be the smallest positive integer such that n
divides 2  1. Also, the element  is a primitive
m
m
nth root of unity in GF (2 ). An (n, k, d) binary QR
code is a cyclic code with the generator polynomial
of the form
g ( x)   ( x   i ).
iQ
(n, k, d) Binary Quadratic
Residue (QR) Codes(4/6)
(n, k, d) Binary Quadratic
Residue (QR) Codes(5/6)
0
10
QR23
QR47
QR89
QR113
-1
10
-2
Pb
10
-3
10
-4
10
-5
10
0
1
2
3
4
Eb/No (dB)
5
6
7
8
Bit Error Probability Pb versus Eb/N0 for the (113, 57, 15), (89, 45, 17), (47, 24,
11), and (23, 12, 7) QR codes with the hard-decision decoder.
(n, k, d) Binary Quadratic Residue
(QR) Codes(6/6)

Recently, six decoders for the QR codes with
parameters (71, 36, 11), (79, 40, 15), (97, 49, 15),
(103, 52, 19), (113, 57, 15), and (89, 45, 17) have
been proposed by Truong et al.

All binary QR codes of lengths less than or equal to
113 are then decoded.
Publisher Papers of QR Codes(1/2)
[1]
Trieu-Kien Truong, Chong-Dao Lee, Yaotsu Chang, and Wen-Ku Su, "A
New Scheme to Determine the Weight Distributions of Binary Extended
Quadratic Residue Codes," IEEE Transactions on Communications , vol.57,
no.5, pp.1221-1224, 2009.5
[2]
Trieu-Kien Truong, Pei-Yu Shih, Wen-Ku Su, Chong-Dao Lee, an Yaotsu
Chang, "Algebraic Decoding of the (89, 45, 17) Quadratic Residue Code,"
IEEE Transactions on Information Theory , vol.54, no.11, pp.5005-5011,
2008.11
C.D. Lee, Yaotsu Chang, and T.K. Truong, "A Result on the Weight
Distributions of Binary Quadratic Residue Codes," Designs, Codes and
Cryptography , vol.42, pp.15-20, 2007.1
Y.H. Chen, T.K. Truong, Y. Chang, C.D. Lee and S.H. Chen, "Algebraic
Decoding of Quadratic Residue Codes Using Berlekamp-Massey
Algorithm," Journal of Information Science and Engineering , vol.23, pp.127145, 2007.1
T.K. Truong, Y. Chang, Y.H. Chen and C.D. Lee, "Algebraic Decoding of
(103,52,19) and (113,57,15) Quadratic Residue Code," IEEE Trans. on
Communications , vol.53, no.5, pp.749-754, 2005.5
[3]
[4]
[5]
Publisher Papers of QR Codes(2/2)
[6] T.K. Truong, Y. Chang, and C.D. Lee, "The Weight Distributions of Some
Binary Quadratic Residue Codes," IEEE Trans. on Information Theory ,
vol.51, no.9, pp.1776-1782, 2005.5
[7] T.K. Truong, Y.Chang, I.S.Reed, H.Y.Cheng and C.D.Lee, "Algebraic
Decoding of (71,36,11), (79,40,15), and (97,49,15) Quadratic Residue
Codes," IEEE Trans. on Communications , vol.51, no.9, pp.1463-1473,
2003.9
[8] Ruhua He, Irving S. Reed, Trieu-Kien Truong, and Xuemin Chen, "Decoding
the (47,24,11) Quadratic Residue Code," IEEE Trans. on Information Theory ,
vol.47, no.3, pp.1181-1186, 2001.3
[9] X. Chen and I.S. Reed, and T.K. Truong, "Decoding the (73,37,13) Quadratic
Residue Code," IEE Proceedings-Computer Digital Techniques , vol.141,
no.5, pp.253-258, 1994.9
[10] I.S.Reed, T.K.Truong, X.Chen, and X.Yin, "Algebraic Decoding of the
(41,21,9) Quadratic Residue Code," IEEE Trans. on Information Theory,
vol.38, no.3, pp.974-986, 1992.5
[11] I.S.Reed, X.Yin, and T.K. Truong, "Algebranic Decoding of the (32,16,8)
Quadratic Residue Code," IEEE Trans. on Information Theory , vol.36, no.4,
pp.876-880, 1990.7
[12] I.S. Reed, X. Yin, and T.K. Truong, J.K. Holmes, "Decoding the (24,12,8)
Golay code," IEE Proceedings-Computers and Digital Techniques , vol.137,
no.3, pp.202-206, 1990.5
Publisher Papers of RS Codes(1/2)







Tsung-Ching Lin, Pei-Ding Chen, and Trieu-Kien Truong, "Simplified
Procedure for Decoding Nonsystematic Reed-Solomon Codes over GF(2^m)
Using Euclid's Algorithm and the Fast Fourier Transform," IEEE
Transactions on Communications , vol.57, no.6, pp.1588-1592, 2009.6
T.C. Lin, T.K. Truong, and P.D. Chen, "A Fast Algorithm for the Syndrome
Calculation in Algebraic Decoding of Reed-Solomon Codes," IEEE Trans.
on Communications , vol.55, no.12, pp.2240-2244, 2007.12
T.K. Truong, P.D. Chen, L.J. Wang, and T.C. Cheng, "Fast Transform for
Decoding Bogh Errors and Erasures of Reed-Solomon Codes Over GF(2m)
for 8≦m≦10," IEEE Transactions on Communications , vol.54, no.2,
pp.181-186, 2006.2
Y.W. Chang、T.K. Truong、J.H. Jeng, "VLSI Architecture of Modified
Euclidean Algorithm for Reed-Solomon Code," Information Sciences ,
vol.155, no.Issues 1-2, pp.139-150, 2003.10
T.-K. Truong, J.-H. Jeng, and T. C. Cheng, "A New Decoding Algorithm for
Correcting Both Erasures and Errors of Reed-Solomon Codes," IEEE Trans.
on Communications , vol.51, no.3, pp.381-388, 2003.3
Lung-Jen Wang, Wen-Shyong Hsieh, Trieu-Kien Truong, and Irving S. Reed,
and T. C. Cheng, "A Fast and Efficient Computation of Cubic-Spline
Interpolation in Image Codec," IEEE Trans. on Signal Processing , vol.49,
no.6, pp.1189-1197, 2001.6
Trieu-Kien Truong, Jyh-Horng Jeng, Irving S. Reed, "Fast Algorithm for
Computing the Roots of Error Locator Polynomials to Degree 11 in ReedSolomon Decoders," IEEE Trans. on Communications , vol.49, no.5, pp.
779-783, 2001.5
Publisher Papers of RS Codes(2/2)






Jyh-Horng Jeng, and Trieu-Kien Truong, "On decoding of both errors and
erasures of a Reed-Solomon code using an inverse-free Berlekamp-Massey
algorithm," IEEE Trans. on Communications , vol.47, no.10, pp.1488-1494,
1999.10
T.K. Truong, R.L Miller and I.S.Reed, "Fast Technique for Computing
Syndromes of BCH and Reed-Solomon Codes," Electronics Letters , vol.15,
no.22, pp.720-721, 1997.1
C.C. Hsu, I.S. Reed, and T.K. Truong, "Inverse Z-Transform by Mobius
Inversion and the Error Bounds of Aliasing in Sampling,," IEEE Trans. on
Signal Processing , vol.42, no.10, pp.2823-2831, 1994.10
C.C. Hsu, I.S. Reed, and T.K. Truong, "Error Correction Capabilities of
Binary Mapped Reed-Solomon Codes with Parity Bits Appended to All
Symbols," IEE Proceedings- Communications, vol.141, no.4, pp.209-211,
1994.8
A. Shiozaki, T.K. Truong, K.M. Cheung, and I.S. Reed, "Fast Transform
Decoding of Nonsystematic Reed-Solomon Codes," IEE ProceedingsComputers and Digital Techniques , vol.137, no.2, pp.139-143, 1990.3
T.K. Truong, W.L. Eastman, I.S. Reed, and I.S. Hsu, "Simplified Procedure
for Correcting Both Errors and Erasures of Reed-Solomon Codes Using
Euclidean Algorithm," IEE Proceedings , vol.135, Pt. E, no.6, pp.318-324,
1988.11
The End
That’s all folks.
Thank you very much!
.
Decoder of linear codes (1/3)




Consider an (n, k) linear code with generator
matrix G= P I k  .
Parity-check matrix H= I nk P T  and c．HT=0
The received vector r=c+e, where c and e
are the transmitted codeword and error
pattern, respectively.
The syndrome of r is
s=r．HT=(c+e)．HT=c．HT +e．HT= e．HT
Decoder of linear codes (2/3)

Consider a (6, 3) linear code generated by
0 1 1 1 0 0 
G  1 0 1 0 1 0  [ P I 3 ]
1 1 0 0 0 1

Its parity-check matrix is
1 0 0 0 1 1
T


H  0 1 0 1 0 1   [ I 3 P ]
0 0 1 1 1 0
Decoder of linear codes (3/3)
Syndrome look-up table
syndrome
s
(s0, s1, s2)
Correctable error patterns
(e0, e1, e2, e3, e4, e5)
(0, 0, 0)
(0, 0, 0, 0, 0, 0)
(1, 0, 0)
(1, 0, 0, 0, 0, 0)
(0, 1, 0)
(0, 1, 0, 0, 0, 0)
(0, 0, 1)
(0, 0, 1, 0, 0, 0)
(0, 1, 1)
(0, 0, 0, 1, 0, 0)
(1, 0, 1)
(0, 0, 0, 0, 1, 0)
(1, 1, 0)
(0, 0, 0, 0, 0, 1)
(1, 1, 1)
(1, 0, 0, 1, 0, 0)