Transcript presentaion(4wp).

ITEMS TO BE DISCUSSED
1.0 OVERVIEW OF CODING STRENGTH (3MINS)
 Weight/distance of binary vectors
 Error detection and correction
 Weight distribution
 Errasure correction
2.0 CYCLIC CODING (4mins)
 Cyclic codes structure and their binary properties
 Systematic cyclic encoding and dividing circuits
3.0 (N-K)-STAGE SHIFT REGISTER CODING (3mins)
 Error detection with an (n-k)-stage shift register
Error detection/correction
FOUR WEEK PROJECT
1
1.0 CODING STRENGTH (3MINS)
WEIGHT/DISTANCE OF BINARY VECTORS
 Hamming weight, w(U): number of nonzero elements in
U.
 For a binary vector w(U) equals the number of ones in
the vector.
 Hamming distance between two codes U and V, d(U,V):
defines the number of elements in which they differ.
 The minimum distance of a code gives a measure of the
codes minimum capability and determines the codes
strength.
Error detection/correction
FOUR WEEK PROJECT
2
1.0 ERROR DETECTION AND CORRECTION
(4MINS)
ERROR DETECTION AND CORRECTION
 Task of the decoder after recieving the vector r, is the
estimation of the transmitted code Ui.
 Maximum likelihood algorithm can be used to express
the optimal decoder algorithm.
 Generally, the error correcting capability of a code t, is
defined as the maximum number of guaranteed
correctable errors per code word and it is related to the
minimum distance between two codes vectors.
as :
t=(dmin-1)/2
Error detection/correction
FOUR WEEK PROJECT
3
1.0 ERROR DETECTION AND CORRECTION
(4MINS)
ERROR DETECTION AND CORRECTION
 In general, a t-error-correcting (n-k) linear code is
capable of correcting a total of 2^(n-k) error patterns.


Error detecting-capability, e, of a code related to
minimum distance between two vectors may be
expressed as:
e = dmin-1
If Aj is the number of code vectors of weight j within an
(n,k) linear code, then, the numbers Ao, A1,A2,….,An are
termed the weight distribution of the code.
Error detection/correction
FOUR WEEK PROJECT
4
2.0 CYCLIC CODING (4mins)
CYCLIC CODES STRUCTURE/ BINARY PROPERTIES
 Defn: Subclass of linear block codes,
General characteristics
 Readily implemented with feedback registers
 Syndrome calculation easily done with feedback shifts
 Algebraic structure of cyclic codes lends to efficient
coding procedures
 Components of (n, k) linear code vector can be treated
as coeffient of a polynomial.
 Where the polynomial function only serves as a
placeholder for the code vector digits.
Error detection/correction
FOUR WEEK PROJECT
5
2.0 CYCLIC CODING (4mins)
SYSTEMATIC CYCLIC ENCODING



Cyclic shift of a code vector: given n, and i, the
remainder or end round shift could be obtained
analytically.
Similarly, cyclic code could be obtained using the
generator polynomial. Cyclic code using a systematic
encoding procedure leads to a reduction in coding
complexity.
Message digits are utilized as part of the code vector
whereby the message digit is shifted into the rightmost k
stages of a codeword register, where the parity digits are
appended by placing them in the leftmost n-k stages.
Error detection/correction
FOUR WEEK PROJECT
6
2.0 CYCLIC CODING (4mins)
SYSTEMATIC CYCLIC ENCODING
Example of cyclic code in systematic form:
http://www.itu.dk/people/beboe03/example1.htm
 Cyclic shift of a codeword polynomial and encoding of a
message polynomial requires a division of one
polynomial by another. What dividing circuit method does
is to make such an operation even easier by by
employing a feedback shift register.
 Computes parity bits
 Computes Message bits

Error detection/correction
FOUR WEEK PROJECT
7
3.0 (N-K)-STAGE SHIFT REGISTER CODING (3mins)
SYSTEMATIC CYCLIC ENCODING WITH AN (N-K)-STAGE SHIFT REGISTER

Cyclic coding in systematic form dealt with computation
of essentially, parity bits due to division of an upshifted
message polynomial by a generator polynomial.

Here we deal with upshifting of the message bits by n-k
positions which computes only the parity bits.
The parity polynomial is the only remainder after division
by generator polynomial which can be found at the
register after n shifts through the n-k shifts stage
feedback.

Error detection/correction
FOUR WEEK PROJECT
8
3.0 (N-K)-STAGE SHIFT REGISTER CODING
(3mins)
SYSTEMATIC CYCLIC ENCODING WITH AN (n-k)-STAGE SHIFT REGISTER
Example of systematic cyclic encoding with (n-k)-stage
shift register

http://www.itu.dk/people/beboe03/example2.htm
Error detection/correction
FOUR WEEK PROJECT
9