EE 6309: VLSI SYSTEMS

Prof. Tony T. Kim

Nanyang Technological University
School of Electrical and Electronic Engineering

http://sites.google.com/view/tonykim
thkim@ntu.edu.sg

1
 Instructor
• Name: KIM, Tae Hyoung (Tony)
• Email: thkim@ntu.edu.sg

• Joined NTU as an assistant professor in Nov. 2009

• Degree: PhD from Univ. of Minnesota in Oct. 2009
– Subthreshold digital circuits and SRAMs
– Circuit reliability monitors
• Experience
– Broadcom, Minneapolis, USA, 2009
– IBM Watson Research Center, NY, USA, 2007, 2008
– Samsung Electronics, Korea, 2001~2005

2
 Moore’s Law

Intel founder and chairman Gordon E. Moore predicted in 1965

that the number of transistors on a chip will double every 18-24
months.

3
 History of the Transistor
First IC:
Jack Kilby
(1958, TI)

Inventor of the transistor:

John Bardeen,
William Shockley,
and Walter Brattain
(1947 at the Bell Lab.)

Intel 45-nm CMOS Technology

4
 Transistor Scaling
Source: www.intel.com

Transistor scaling is getting slow down due to many challenging

issues such as performance, power, reliability, variability,
cost/yield, and physical issues.

5
 Constant Field Scaling
• To mitigate aggravated short-channel effects

Device and circuit parameters Factor

Device dimensions (tox, L, W, Xj) 1/k

Scaling
Doping concentration (Na, Nd) k
Assumptions
Voltage (V) 1/k

Electric field (E) 1

Device Capacitance (C=εA/t) 1/k
Parameters Current (I) 1/k
Channel resistance (Rch) 1

Delay (CV/I) 1/k

Power (VI) 1/k2
Circuit
Switching energy (CV2) 1/k3
Parameters
Circuit density (1/A) k2
Power density (P/A) 1

6
 Constant Voltage Scaling
• To achieve higher clock speed

Device and circuit parameters Factor

Device dimensions (tox, L, W, Xj) 1/k

Scaling
Doping concentration (Na, Nd) k
Assumptions
Voltage (V) 1

Electric field (E) k

Device Capacitance (C=εA/t) 1/k
Parameters Current (I) k
Channel resistance (Rch) 1/k

Delay (CV/I) 1/k2

Power (VI) k
Circuit
Switching energy (CV2) 1/k
Parameters
Circuit density (1/A) k2
Power density (P/A) k3

7
 Constant Voltage Scaling
• More aggressive scaling than constant field
• Limitations
– Reliability problems due to high field
– Power density increases too fast

• Both constant field and constant voltage scaling

have been followed in practice
• Field and power density has gone up as a byproduct
of high performance, but till now designers are able
to handle the problems

8
 History of CPU: 4004
• First microprocessor (1971)
- For Busicom calculator
• Characteristics
- 10 m process
- 2300 transistors
- 400 – 800 kHz
- 4-bit word size
- 16-pin DIP package
• Masks hand cut from Rubylith
- Drawn with color pencils
- 1 metal, 1 poly (jumpers)
- Diagonal lines (!)

Source: www.intel.com
9
 History of CPU: Pentium 4
• Deep pipeline (2001)
– Very fast clock
– 256-1024 KB L2$
• Characteristics
– 180 – 65 nm process
– 42-125M transistors
– 1.4-3.4 GHz
– Up to 160 W
– 32/64-bit word size
– 478-pin PGA
• Units start to become
invisible on this scale
Source: www.intel.com
10
 History of CPU: Pentium M
• Pentium III derivative
– Better power efficiency
– 1-2 MB L2$
• Characteristics
– 130 – 90 nm process
– 140M transistors
– 0.9-2.3 GHz
– 6-25 W
– 32-bit word size
– 478-pin PGA
• Cache dominates chip area

Source: www.intel.com

11
 History of CPU: Core i7
• Quad core (& more)
– Pentium-style architecture
– 2 MB L3$ / core
• Characteristics
– 45-32 nm process
– 731M transistors
– 2.66-3.33+ GHz
– Up to 130 W
– 32/64 bit word size
– 1366-pin LGA
– Multithreading
• On-die memory controller

Source: www.intel.com
12
 Course Topics
PART #1
1. DATA CODING
2. NOISE IN DIGITAL SYSTEMS
3. FAULT MODELS
4. FAULT SIMULATION

PART #2
5. SYNCHRONIZATION
6. PARALLEL PROCESSING
7. MEMORY MANAGEMENT

13
 EE 4340: Topic #1
DATA CODING

Prof. Tony T. Kim

Nanyang Technological University
School of Electrical and Electronic Engineering

http://sites.google.com/view/tonykim
thkim@ntu.edu.sg

14
 Data Coding
Objective: To avoid errors during digital signal
transmission from a source to a destination
•Sources of Transmission Error
– Noisy channel
– Component failure
– Power interruption
•Types of Error
– Single-bit error
– Multi-bit error (or Burst error)
•Reference
– ‘Understanding Data Communication and Networks, PWS,
William A. Shay

15
 Data Coding
• Data Coding
– Error Detection Coding
– Error Correction Coding
– Data Encryption and Decryption (will not be covered.)

• Error Detection Coding

– Parity Checking
– Cyclic Redundancy Checks (CRC) Codes
– M-Out-Of-N Code

• Error Correction Coding

– Hamming Codes

16
 Data Coding
• Description
– Adding extra check bit(s) to the original data bits
– Forming a set of valid code-word for the purpose of error
detection and correction
– An invalid code-word received indicates the existence of
error bit(s)
• Error Detection
– The process of detecting an invalid code-word
– Parity checking, Cyclic redundancy checking
• Error Correction
– The process of restoring the corrupted bit(s) of an invalid
code-word
– Hamming codes

17
 Self-Checking
• Self-checking: the capability to verify automatically
whether there is any fault without the need of externally
applied test stimuli
• Self-checking design can be achieved by using error-
detecting codes
– During normal fault-free operation, the logic network receives only
a subset of input code & produces a subset of output code – valid
code word
– A non-code word indicates the presence of a fault
– A fault may also result in an (incorrect) code word, rather than a
non-code word – undetectable fault

18
 Totally Self-Checking Circuit
• Fault-Secure circuit: For any fault from a given set of faults,
the circuit never produces an incorrect code word
• Self-Testing circuit: For every fault from a given set of faults,
the circuit produces a non-code word at the output for at
least one input code word
• A circuit is totally self-checking if it is both fault-secure &
self-testing: during normal operation all faults from a given
set would cause a detectable, erroneous output

19
 Totally Self-Checking Circuit
• Temporary faults and permanent faults are
detected
• Faults are immediately detected upon occurrence

Checker checks
the validity of the output
code words

20
 Example
• Totally self-checking checker has 2 outputs and
hence, 4 output combinations. Two of these output
combinations are considered as valid (01,10). A
non-valid output, 00 or 11 indicates either a non-
code word at the input or a fault in the checker
itself.

21
 Two-Rail Checker
• Two groups of inputs: (x1,x2,…,xn) & (y1,y2,…,yn)
• Two outputs: f & g
• The signals observed at f & g should always be
complementary if and only if every pair xi, yi is
complementary for all i (1≤i ≤n)

f = x0y0 + x1y0

g = x0x1 + y0y1

22
 Two-Rail Checker

• In an error-free situation when

x0x1=11, y0y1=00, f =0, g = 1
x0x1=10, y0y1=01, f =1, g = 0
• In an erroneous situation
x0x1=11, y0y1=10, f =1, g =1
• A non-code output indicates an error

23
 Multi-Level Tree Checker
• A two-rail checker for an arbitrary number of input
pairs may be designed using two-level AND-OR
logic
• A tree checker realized by interconnecting the
checker modules with two input pairs is more
efficient
• A general multi-level tree checker with m input
pairs formed by interconnecting two-rail checker
modules, requires (m-1) modules and log2m
module levels

24
 Example
• A tree checker with m=6, formed by
interconnecting two-rail checker modules
• No. of checker modules required m-1=6-1=5
• No. of Levels required log2m= log26≈3

25
 Parity Checking
• Most common technique for single-bit error
detection

• Addition of ONE parity bit to the original data bits

• Types of parity checking

EVEN PARITY ODD PARITY

Total number of 1-bits in the Total number of 1-bits in the

data and parity bit is EVEN data and parity bit is ODD

26
 Parity Checking
• Calculation
– For an n-bit data string ( bn-1 bn-2 ..... b2 b1 b0 ), the parity
bits for the Even and Odd Parity Checks are defined as:
PEVEN = bn-1  bn-2  .....  b2  b1  b0

PODD = bn-1  bn-2  .....  b2  b1  b0

• Example
Data Bits Parity Bit
11010100 0 Even Parity
11010100 1 Odd Parity

27
 BCD Codes with Parity Bits
Decimal No. BCD BCD with EP BCD with OP
0 0000 0000 0 0000 1
1 0001 0001 1 0001 0
2 0010 0010 1 0010 0
3 0011 0011 0 0011 1
4 0100 0100 1 0100 0
5 0101 0101 0 0101 1
6 0110 0110 0 0110 1
7 0111 0111 1 0111 0
8 1000 1000 1 1000 0
9 1001 1001 0 1001 1
28
 Error Detection
• Transmitter
– The parity bit is sent together with the data bits (forming
the code-word)
• Receiver
– An error signal (E) is generated from the code-word
received, which is defined as:
EEVEN = bn-1  bn-2  .....  b2  b1  b0  PEVEN

EODD = bn-1  bn-2  .....  b2  b1  b0  PODD

if E = 0: No error
E = 1: Error

29
 Hardware Implementation
• Even Parity + 4-bit Data

1 0 0 0 1 0 0 1 1

1 0 1 1

0
1
- Generator -
1
• Exercise: Odd Parity? - Detector-

30
 Hardware Implementation
• Serial Data Transmission
– Calculate parity bit using the transmitted bits
– Minimum delay for parity bit generation

31
Pros and Cons of Parity Checking
• Wide Usage in Computer Systems
– Each bit travels through different paths
– One faulty path will be detected
• Ability to Detect Any Single-bit Error
– In fact, able to detect all odd number of bit errors

• Disability to Detect Any Even Number of Bit Errors

• Too Low Coverage
– Only 50% of multi-bit or burst errors are detected.
• Additional Memory Space Required for Parity Bits

32
 2-D Parity Checks
• Block Check Codes
– Form data in 2-D code-words
– Generate both row and column parity bits (Transmitter)
– Execute both row and column parity checks (Receiver)
– Position of a single-bit error can be identified
– Single-bit error can be corrected
– Position of multi-bit errors cannot be identified
– Multi-bit errors can be detected
– Assembling and disassembling of data block is required

33
 2-D Parity Checks: Example
• Transmitter Row Parity Bits

1st 0 1 1 0 0
2nd 1 1 0 0 0
3rd 1 1 1 0 1
4th 0 0 0 0 0
0 1 0 0 X

Col. Parity Bits

34
 2-D Parity Checks: Example
• Receiver Row Error Bits

1st 0 1 1 0 0 0
2nd 1 1 0 0 0 0
3rd 1 1 0 0 1 1
4th 0 0 0 0 0 0
0 1 0 0 X
0 0 1 0

Col. Error Bits : Error Bit

Parity check fails in the 3rd row and 3rd column.
This allows for error correction.
35
 2-D Parity Checks: Practice
• Receiver Row Error Bits

1st 0 1 1 0 0 ?
2nd 1 1 1 0 0 ?
3rd 1 1 0 0 1 ?
4th 0 0 0 0 0 ?
0 1 0 0 X
? ? ? ?

Col. Error Bits : Error Bit

Multi-bit errors can be detected.
But, they cannot be corrected.
36
 2-D Parity Checks: Practice
• Receiver Row Error Bits

1st 0 1 1 0 0 0
2nd 1 1 1 0 0 1
3rd 1 1 0 0 1 1
4th 0 0 0 0 0 0
0 1 0 0 X
0 0 0 0

Col. Error Bits : Error Bit

Multi-bit errors can be detected.
But, they cannot be corrected.
37
 Distance
• Distance
– The number of bit(s) to change in one word to be identical
to the other word

• Hamming Distance
– The smallest number of bit(s) in which any two words differ
in a code

• Minimum Distance Requirements

– Two or more for an error detection
– Three or more for an error correction
– Four or more for double-bit error detection

38
 Hamming Distance: Example
Min. Distance Error Detect
BCD code 1 No
BCD code w/
2 Single-bit
one parity bit

• Example
– Consider a simple 3-bit code with the minimum distance of
3, where only two valid code-words exist:
1 1 1 (a)
0 0 0 (b)
– After a single error, (a) becomes:
1 1 0 (a)
– Minimum difference is still 2, which can correct the error.

39
 Hamming Distance: Practice
• 8-bit Code-word
Hamming Detect
a b c d e f g h
Distance /Correct
A 1 1 1 1 1 1 1 1 X X
B 1 1 1 1 1 0 1 1
BERR 1 1 1 1 1 1 1 1
C 1 1 1 0 1 0 1 1
CERR 1 1 1 1 1 0 1 1
D 1 0 1 0 1 0 1 1
DERR 1 1 1 0 1 0 1 1
E 1 0 1 0 1 0 1 0
EERR 1 1 1 0 1 0 1 1

40
 Hamming Distance: Practice
• 8-bit Code-word
Hamming Detect
a b c d e f g h
Distance /Correct
A 1 1 1 1 1 1 1 1 X X
B 1 1 1 1 1 0 1 1 1 X
BERR 1 1 1 1 1 1 1 1
C 1 1 1 0 1 0 1 1 2 1-bit detect
CERR 1 1 1 1 1 0 1 1 d or f?
D 1 0 1 0 1 0 1 1 3 1-bit correct
DERR 1 1 1 0 1 0 1 1 b
E 1 0 1 0 1 0 1 0 4 2-bit detect
EERR 1 1 1 0 1 0 1 1 (b,h) or (d,f)?

41
 Hamming Codes
• For an error correction, desirable to detect and
locate error(s)
• HAMMING CODES: one of the commonly used error
correction code
• Creation of special code-words from data string
• Insertion of multiple parity bits in code-word
• Each parity bit checks parity in strategic location
• Overlapping of bits checked
• Combination of parity check failures indicates bit(s)
for correction

42
Hamming Codes: 1-bit Correction
1. To each group of m message bits, k parity bits P1 P2 ... Pk are
added to form an ( m + k ) code
2. Each bit of the code-word is assigned a decimal location
number from 1 to ( m + k ), starting from LSB
3. k parity checks are performed on specific bits of each code-
word
4. The parity checks allow the development of a position binary
number ( bk-1 ... b1 b0 ) , whose value (when an error occurs)
will identify the location of the error
5. The number of k parity bits must be large enough to identify
any one of the possible ( m + k ) single error, and identify “ no
error ” with decimal value zero.
2k  m+k+1
6. The parity bits are placed in positions 1, 2, 4 ... 2 k-1 of the
code-word

43
 1-bit Correction: Example
• BCD code ( m = 4 ) using Even parity checks
k = 3 since 2 3  4 + 3 + 1
• Parity bit positions = 1, 2, 4

Hamming Code
Position 7 6 5 4 3 2 1
Code-word M4 M3 M2 P3 M1 P2 P1

44
 1-bit Correction: Example
• Definition of 3 Parity Bits
– P1: even parity in bits 1, 3, 5, and 7 (P1=M1M2M4)
– P2: even parity in bits 2, 3, 6, and 7 (P1=M1M3M4)
– P3: even parity in bits 4, 5, 6, and 7 (P1=M2M3M4)
• Example: BCD code ‘0110’
Position 7 6 5 4 3 2 1
Code-word M4 M3 M2 P3 M1 P2 P1
BCD Code 0 1 1 0
Parity (1,3,5,7) √ √ √ 1
Parity (1,3,5,7) √ √ √ 1
Parity (1,3,5,7) √ √ √ 0
Hamming Code 0 1 1 0 0 1 1

45
 Hamming Code-words: BCD
• 1-bit Error Correction Using Even Parity Checks
Position 7 6 5 4 3 2 1
Decimal Value M4 M3 M2 P3 M1 P2 P1
0 0 0 0 0
1 0 0 0 1
2 0 0 1 0
3 0 0 1 1
4 0 1 0 0
5 0 1 0 1
6 0 1 1 0
7 0 1 1 1
8 1 0 0 0
9 1 0 0 1
46
 Hamming Code-words: BCD
• 1-bit Error Correction Using Even Parity Checks
Position 7 6 5 4 3 2 1
Decimal Value M4 M3 M2 P3 M1 P2 P1
0 0 0 0 0 0 0 0
1 0 0 0 0 1 1 1
2 0 0 1 1 0 0 1
3 0 0 1 1 1 1 0
4 0 1 0 1 0 1 0
5 0 1 0 1 1 0 1
6 0 1 1 0 0 1 1
7 0 1 1 0 1 0 0
8 1 0 0 1 0 1 1
9 1 0 0 1 1 0 0
47
 Hardware Implementation
• M = 4, k = 3

M4 M3 M2 M1 Y7 Y6 Y5 Y4 Y3 Y2 Y1

Generator (Tx) Receiver (Rx)

M4 M3 M2 P3 M1 P2 P1 M4 M3 M2 M1

Parity bits P1, P2, and P3 can be easily generated

using XOR gates. (Refer to the previous lecture)

48
 Hardware Implementation
• Hamming Code Generation (m=4, k=3)

49
 Hardware Implementation
• M = 4, k = 3

M4 M3 M2 M1 Y7 Y6 Y5 Y4 Y3 Y2 Y1

Generator (Tx) Receiver (Rx)

M4 M3 M2 P3 M1 P2 P1 M4 M3 M2 M1

Message bits M1, M2, M3, and M4 can be easily

generated checking parity.

50
 1-bit Correction: Example
• Position Binary Number (Receiver)
Error Position B2 B1 B0
0 0 0 0
1 0 0 1
2 0 1 0
3 0 1 1
4 1 0 0
5 1 0 1
6 1 1 0
7 1 1 1
– B0 = 1: an error in either of positions 1, 3, 5, and 7
– B1 = 1: an error in either of positions 2, 3, 6, and 7
– B2 = 1: an error in either of positions 4, 5, 6, and 7
51
 Error Detection
• To Detect and Locate Single-bit Error
– Perform parity checks on the incoming code-word
– Generate the position binary number ( bk-1 ... b1 b0 )
– With m = 4 and k = 3, the position binary number is ( b2b1b0 )
• Error Detection and Location Flow
Transmitted Data Received Data Parity check for bits 1, 3, 5, 7
(0110011) (0110111) B0 = 1

Parity check for bits 2, 3, 6, 7

B1 = 1

Corrected Data B2B1B0=011 Parity check for bits 4, 5, 6, 7

(0110011) Error Position = 3 B2 = 0

52
 Hardware Implementation
• Position Binary Number Generator (M = 4, k = 3)

b2=Y7Y6 Y5 Y4
b1=Y7Y6 Y3 Y2
b0=Y7Y5 Y3 Y1

53
 Error Correction
• To Correct Error
– Using position binary number ( bk-1 ... b1 b0 )
– Error correction is done by simply inverting the error bit
– Only data bits (M4, M3, M2, M1) need to be corrected
• Error Correction Flow
Transmitted Data Received Data Parity check for bits 1, 3, 5, 7
(0110011) (0110111) B0 = 1

Parity check for bits 2, 3, 6, 7

B1 = 1

Corrected Data B2B1B0=011 Parity check for bits 4, 5, 6, 7

(0110011) Error Position = 3 B2 = 0

54
 Hardware Implementation
• Error Correction (M = 4, k = 3)

55
 Hardware Implementation
• Hamming Code Error Correction (m=4, k=3)

56
Hamming Codes: Double-bit Error
• Hamming code with m=4 and k=3 can detect and
correct any single-bit error.
• If double-bit error?
Position 7 6 5 4 3 2 1 position
Code-word M4 M3 M2 P3 M1 P2 P1
BCD Code 0 1 1 0
Hamming Code 0 1 1 0 0 1 1
Code at Rcv. 0 1 0 0 1 1 1
b0 0 0 1 1 0
b1 0 1 1 1 1
b2 0 1 0 0 1
(b2, b1, b0) = (1,1,0) pointing a wrong position.

57
Hamming Codes: Double-bit Error
• To identify double-bit errors, the minimum distance
should be 4 (k = 4)
• Additional parity check bit (P4) at the position of 8.
Position 8 7 6 5 4 3 2 1 b2,b1,b0
Code-word P4 M4 M3 M2 P3 M1 P2 P1
BCD Code 0 1 1 0
Hamming Code 0 0 1 1 0 0 1 1
No Error 0 0 1 1 0 0 1 1 0, 0, 0
Single-bit Error 0 0 1 1 0 1 1 1 0, 1, 1
Single-bit Error 1 0 1 1 0 0 1 1 0, 0, 0
If P4 parity check fails
If (b2,b1,b0) = (0,0,0), error in P4
Else, error in the position of (b2,b1,b0)
58
Hamming Codes: Double-bit Error
• Double-bit Error Detect
P4 parity check OK and (b2,b1,b0)  (0,0,0)
Position 8 7 6 5 4 3 2 1 b2,b1,b0
Code-word P4 M4 M3 M2 P3 M1 P2 P1
BCD Code 0 1 1 0
Hamming Code 0 0 1 1 0 0 1 1
Double-bit Error
0 1 1 1 0 1 1 1 1, 0, 0
Case #1
Double-bit Error
1 0 1 1 1 0 1 1 1, 0, 0
Case #2
Note: if error in P4, (b2, b1, b0) indicates the location of the
second error bit
• Exercise: Circuit design of single-bit error correction
and double-bit error detection for m=4
59
 Hamming Code Capability
Minimum Distance Capability

1 No Error Detection

2 Single Error Detection

3 Single Error Correction

Single Error Correction

4
and Double Error Detection

• For k-bit error detection, minimum distance  k+1

– Without error correction capability
• For k-bit error correction, minimum distance  2k+1
• Hamming codes for multi-bit error correction?
– Yes, but not covered in this course
60
 Minimum Distance Summary
• Following summarizes the minimum distance
requirements for error corrections or detections
• Detection capability can be improved by degrading
correction capability. The other way does not work.
Minimum Corrected Detected Detection
Distance Bit(s) Bit(s) only
1 0 0 0
2 0 1 1
3 1 1 2
4 1 2 3
5 2 2 4
6 2 3 5
7 3 3 6
8 3 4 7
d (d-1)/2 d/2 d-1

61
 Code Efficiency & Redundancy
• For a code-word with (m, k) bits,
Code Efficiency = m / (m + k)
Code Redundancy = k / (m + k)

• Hamming code for single-error correction

m k m+k Efficiency Redundancy
4 3 7 0.57 0.43
8 4 12 0.67 0.33
16 5 21 0.76 0.24
32 6 38 0.84 0.16
64 7 71 0.90 0.10

62
 Hamming Code: Practice
• A digital communication link has the
following specifications:
– 7-bit message string denoted as (M7, … , M1)
– Error detection and error correction capability
– One or more check bits
– Even parity for check bits

• Hamming code for message of ‘101 0110’

– Single-bit error correction
– Double-bit error detection

63
 Cyclic Redundancy Check
• Principles
– Polynomial Representation: treat all binary bit
string as a polynomial function of variable (x)
– Polynomial Division: error checking via
“Polynomial Division” using Modulo-2 arithmetic
operation
– Extremely reliable in detecting both single and
multiple bit errors
– Can be implemented efficiently using simple
feedback shift registers and XOR gates

64
 Polynomial Representation
• Given a binary bit string:
B = bn-1 bn-2 … b1 b0
We can represent the bit string as a polynomial
function of a dummy variable (x) which is binary
weighted as follows:
B(x) = bn-1 xn-1 + bn-2 xn-2 + … b1 x + b0

Example: The string (1100101) can be represented as

B(1100101) = x6 + x5 + x2 + x1
•Purpose: To permit mathematical coding
and manipulation of the binary data string,
such as Modulo-2 arithmetic operations.
65
 Modulo-2 Arithmetic
• Addition / Subtraction
– In modulo-2 arithmetic operations, there is no “carry” or “
borrow” as the bits are either ‘0’ or ‘1’. Thus addition and
subtraction operations are identical.
• Example:
Addition: 1011010 x6 x4 x3 x
+ 0101110 + x5 x3 x2 x
1110100 x6 + x5 + x4 x2

Subtraction: 1011010 x6 x4 x3 x
− 0101110 − x5 x3 x2 x
1110100 x6 + x5 + x4 x2

In fact (A + B ) = (A − B) = ( A  B )

66
 Modulo-2 Arithmetic
• Modulo-2 Polynomial Division
– In general, division of a polynomial B(x) by another
polynomial G(x) produces a quotient polynomial Q(x) and a
remainder polynomial R(x):
B(x) R(x)
= Q(x) +
G(x) G(x)

or B(x) = Q(x)  G(x) + R(x)

Since modulo-2 addition = subtraction, we get

B(x) + R(x) = Q(x)  G(x)

This shows that it is possible to add a specific bit pattern R(x)
to the original data string to produce a new polynomial
which is exactly divisible by polynomial G(x).

67
 Modulo-2 Arithmetic
• Example
B(x) = x10 + x9 + x7 + x5 + x4
G(x) = x4 + x3 + 1

x6 + x3 + x
x4 + x3 + 1 ) x10 + x9 + x7 + x5 + x4
x10 + x9 + x6
x7 + x6 + x5 + x4
x7 + x6 + x3
x5 + x4 + x3
x5 + x4 + x
Remainder → x3+ x

We get : Q(x) = x6 + x3 + x
R(x) = x3 + x
Verify : B(x) + R(x) = Q(x)G(x) (Modulo-2 addition)
68
 Modulo-2 Arithmetic
• Synthetic Division Using Bit String
B(x) = x10 + x9 + x7 + x5 + x4 (B = 11010110000)
G(x) = x4 + x3 + 1 (G = 11001)

1 001010
11001 ) 1101 0 110000
1100 1
1 11 1 0
1 10 0 1
1 1 100
1 1 001
Remainder → 1010

We get : Q = 1001010 or Q(x) = x6 + x3 + x

R = 1010 or R(x) = x3 + x

69
 Principles of CRC Code
• At the transmitter end,
T(x) = B(x) + R(x) = Q(x)  G(x)
• At the receiver end
T' (x)
= Q(x) + R ' (x)
G(x)
E(x)
where T' (x) = T(x) + E(x) and R' (x) =
G(x)
If the remainder polynomial R’(x) = 0, it implies that there is no
error. Otherwise, error(s) had occurred during transmission
and re-transmission is needed.

The generator polynomial G(x) is chosen such that it is able to

detect virtually all single and multiple-bit errors, “Burst Error”.

70
 Principles of CRC Code
Transmitter

B(x) + R(x) T(x) = Q(x)G(x)

Receiver

T’(x)
¸ G(x) Q(x) = Q(x) + R’(x)
=T(x) + E(x)

Note: R’(x) = 0, if E(x) = 0, indicating no transmission error

71
 Generation of CRC Code
• Step 1: For a generator polynomial G(x) = gr xr + gn-1
xn-1 + … g1 x + g0 with degree of r, append r number
of ‘0’s to the end of the original data string, forming
new data polynomial B’(x)

• Step 2: Divide B’(x) by the generator polynomial G(x)

to obtain the remainder polynomial R’(x)
B' (x) R ' (x)
= Q' (x) +
G(x) G(x)

• Step 3: Transmit T(x) = B’(x) + R’(x) which is

equivalent to Q’(x)G(x) and is exactly divisible by
G(x)
72
CRC Encoding in Systematic Form
• Let k = number of message bits
r = degree of generator polynomial G(x)
n = total code length (i.e. n = k + r)
• Message Polynomial:
B(x) = bk-1 xk-1 + bk-2 xk-2 + … b1 x + b0

• Generator Polynomial:
G(x) = gr xr + gr-1 xr-1 + … g1 x + g0

• Multiply B(x) by xr:

xr  B(x) = bk-1 xn-1 + bk-2 xn-2 + … b1 xr+1 + b0 xr

73
CRC Encoding in Systematic Form
• Divide xr B(x) by G(x):
xr  B(x) = Q(x)G(x) + R(x)
Where R(x) = rr-1 xr-1 + rr-2 xr-2 + … r1 x + r0

• Add xr B(x) by R(x):

xr B(x) +R(x) = Q(x)G(x)
= bk-1 xn-1 + bk-2 xn-2 + … b1 xr+1 + b0 xr
+ rr-1 xr-1 + rr-2 xr-2 + … r1 x + r0

• CRC Code-word (n-bit)

(bk-1 bk-2 … b1 b0 rr-1 rr-2 … r1 r0)
k message bits r check bits
74
 CRC Encoding: Generation
• Data bits B = 1101011 and G(x) = x4 + x3 + 1 (i.e. r=4)

• Message Polynomial: B(x) = x6 + x5 + x3 + x1 + 1

• Multiply B(x) by x4: x4  B(x) = x10 + x9 + x7 + x5 + x4
• Divide x4 B(x) by G(x):
x10 + x9 + x7 + x5 + x4 6 3 x3 + x
= (x + x + x) +
x4 + x3 + 1 x4 + x3 + 1
• Add x4 B(x) by R(x):
xr B(x) +R(x) = x10 + x9 + x7 + x5 + x4 + x3 + x

• CRC Code-word (n-bit): (1 1 0 1 0 1 1 1 0 1 0)

75
 CRC Encoding: Verification
• With no error, received code-word T’ = 11010111010
T’(x) = x10 + x9 + x7 + x5 + x4 + x3 + x
G(x) = x4 + x3 + 1
1 0 0 1 0 1 0
1 1 0 0 1 ) 1 1 0 1 0 1 1 1 0 1 0
step 1 1 1 0 0 1
0 0 1 1 1
step 2 0 0 0 0 0
0 1 1 1 1
step 3 0 0 0 0 0
1 1 1 1 1
step 4 1 1 0 0 1
0 1 1 0 0
step 5 0 0 0 0 0
1 1 0 0 1
step 6 1 1 0 0 1
0 0 0 0 0
step 7 0 0 0 0 0
0 0 0 0  Remainder
Remainder R(x) = 0  No Error
76
 CRC Encoding: Verification
• With errors, received code-word T’ = 11000001010
T’(x) = x10 + x9 + x3 + x
G(x) = x4 + x3 + 1
1 0 0 0 1 1 1
1 1 0 0 1 ) 1 1 0 0 0 0 0 1 0 1 0
step 1 1 1 0 0 1
0 0 0 1 0
step 2 0 0 0 0 0
0 0 1 0 0
step 3 0 0 0 0 0
0 1 0 0 1
step 4 0 0 0 0 0
1 0 0 1 0
step 5 1 1 0 0 1
1 0 1 1 1
step 6 1 1 0 0 1
1 1 1 0 0
step 7 1 1 0 0 1
0 1 0 1  Remainder
Remainder R(x) = x2 + 1  Errors in Transmission
77
 Analysis of CRC
• We relied on the proposition that a damaged frame
or bit string means that division by generator
polynomial G(x) yields a non-zero remainder.
• Is it possible to change the transmitted bit string T
such that dividing the received polynomial T’(x) by
G(x) does give a zero remainder?
• Yes, but a complete proof requires knowledge of
factorization properties of polynomial rings (a field in
abstract mathematics), which is beyond the scope of
this course.

• Brief discussion on the criteria involved in selection

of the generator polynomial G(x).

78
 Selection of G(x)
• Consider a given generator polynomial:
G(x) = gr xr + gr-1 xr-1 + … g1 x + g0

• Undetected transmission errors correspond to

Errors for which G(x) is a factor of the error
Polynomial, E(x).

• If x is not a factor of G(x), then all burst errors

having length smaller or equal to the degree of G(x)
will be detected.

• If (x + 1) is a factor of G(x), then all burst errors

damaging an odd number of bits will be detected.

79
 Selection of G(x)
• In general, CRC is very effective in performing error
detection if G(x) is chosen properly
• For a generator polynomial G(x) of degree r where x
is not a factor but (x + 1) is a factor, it is able to
detect the following errors :
– All burst errors of length  r
– All burst errors affecting an odd number of bits
– All burst errors of length = r + 1, with probability
( 2r-1 - 1 ) / 2r-1
– All burst errors of length > r + 1, with probability
( 2 r - 1 ) / 2r

( Note: For CRC-32 code, this is equivalent to

99.99999998% accuracy rate !!! )

80
 Standard G(X) Polynomials
• Some of the widely used generator polynomials for
G(x) in local area networks (LANs):

CRC Codes G(x) Polynomial

CRC-12 x12 + x11 + x3 + x2 + x + 1

CRC-16 x16 + x15 + x2 + 1
CRC-CCITT x16 + x12 + x5 + 1
CRC-32 x32 + x26 + x23 + x16 + x12 + x11 + x10
+ x8 + x7 + x5 + x4 + x2 + x + 1

81
 Cyclic Code Generation
• The term ‘cyclic’ is derived from the ring shift
register structure.

• Data cycled through the registers and output is

feedback to the input.

• The bit pattern in the shift registers will present

different patterns as it is clocked by the system
clock (except for the case of all 0’s and 1’s ).

• For an n-bit shift register structure, there can be up

to 2n different bit patterns.

82
 Cyclic Code Generation
• Example: The 4-bit shift register configuration below
will cycles through 4 different bit patterns if initially
loaded with 0001, but not all possible 4-bit patterns.

0001
D Q D Q D Q D Q
0001 1000

Clock 0100

• When XOR gates (performing modulo-2 sum) are

added to the feedback path, the number of possible
bit patterns will increase.

83
 Cyclic Code Generation
• A feedback shift register of n-bit which produces 2n –
1 bit patterns as it is clocked is defined as a
maximum length shift register.

• Maximum length shift register structure possesses

the feature of acting as a divider for any input
sequence.

• Any other circuit which does not provide a maximal

sequence will not perform the division operation.

84
 Cyclic Code Generation
• Example (Maximum Sequence Generation): Consider
the following 3-bit shift register and XOR gate
structure, assuming an initial bit pattern of 001.
Clock Cycle R1 R2 R3
0 0 0 1
1 1 0 1
2 1 1 1
R1 R2 R3
3 1 1 0
4 0 1 1
5 1 0 0
6 0 1 0
7 0 0 1

85
 Cyclic Code Generation
• Example (Divider Circuit with Shift Register and XOR
gate): Consider the same maximum sequence shift
register structure, assuming initial register content
reset to all 0’s and a 4-bit input string 1110 with MSB
checked first: G(x) = x3 + x2 + 1

Clock Input R1 R2 R3
Cycle
0 0 0 0 0
1 1 1 0 0
0111 R1 R2 R3
2 1 1 1 0
3 1 1 1 1
4 0 1 1 0

86
 Cyclic Code Generation
• The bit pattern in registers R3 R2 R1 after 4-shifts
corresponds to the remainder polynomial R(x).

R = (R3, R2, R1) = 0 1 1

 R(x) = x + 1
• Verify:
x3 + x2 + x = 1 + x+1
x3 + x2 + 1 x3 + x2 + 1

87
 Polynomial Divisor Circuit
• Let V(x) = vn-1 xn-1 + vn-2 xn-2 + … v1 x + v0
G(x) = gr xr + gr-1 xr-1 + … g1 x + g0
We want to perform:
V(x) R(x)
= Q(x) +
G(x) G(x)
Use shift register and XOR circuit:
Output

g0 g1 g2 Gr-1 Gr

V(x)

Note: g represents either a connection or no connection

i

depending on gr term in the polynomial G(x) being either ‘1’ or

‘0’ respectively.

88
 Polynomial Divisor Circuit
• Example #1: G(x) = x3 + x2 + 1
g3 = 1, g2 = 1, g1 = 0, g0 = 1
x0 x2 x3 Out

In

• Example #2: G(x) = x3 + x + 1

g3 = 1, g2 = 0, g1 = 1, g0 = 1
x0 x x3 Out

In

89
 Illustration of Division Process
• Using Polynomial Divisor Circuit for Error Detection
– Consider a polynomial divisor circuit for generator
polynomial for the purpose of error detection :
G(x) = x4 + x3 + 1

Assume an incoming bit string T’ and the corresponding

polynomial T’(x) received :
T’ = 11000001010
T’(x) = x10 + x9 + x3 + x
with errors in positions 5, 6 and 8 as discussed in previous
example (refer to page 58).

Assuming MSB of the incoming bit string is shifted in first, a

step-by-step shifting of all bits into the divisor circuit is
shown below.

90
Illustration of Division Process
Out
Initial
Input
0 0 0 0
01010000011(M)
xi 0 1 2 3 Out
Step 0:
Input
0 0 1 1
0101000(M)
xi 0 1 2 3 Out
Step 1:
Input
1 0 0 0
010100(M)
xi 0 1 2 3 Out
Step 2:
Input
0 1 0 0
01010(M)
xi 0 1 2 3
Out
Step 3:
Input
0 0 1 0
0101(M)
xi 0 1 2 3
91
Illustration of Division Process
Out
Step 4:
Input
1 0 0 1
010(M)
xi 0 1 2 3 Out
Step 5:
Input
1 1 0 1
01(M)
xi 0 1 2 3 Out
Step 6:
Input
0 1 1 1
0(M)
xi 0 1 2 3 Out
Step 7:
Input
1 0 1 0
(M)
xi 0 1 2 3
– First 4 (or r) cycles just shift 4 (or r) MSBs of input string.
– After n-shifts (in this example, n = 11), register bit pattern
corresponds to remainder polynomial, R(x)
92
 Reducing the Number of
Shifting Cycles
• The process of shifting the incoming bit string can be reduced
by re-arranging the polynomial divisor circuit, as illustrated
below for the case of
G(x) = x3 + x2 + 1
x0 x2 x3 Out Out

In

-Before- -After- Incoming Bits

• The incoming bit string (MSB first) will be available at the

output when the shifting starts, which is useful when working
as a CRC encoding circuit.
• The above circuit works provided:
g0 = 1 and gr = 1

93
 CRC Encoding:
Using (n-k) Stage Shift Register
• From previous discussion, we want to generate the
CRC code in the following format:
k message bits (n-k) check bits
• This means that the message data are intact, thus no
further assembling of message bits is required.

• This requires the encoding circuitry to output the

first k message bits followed by the (n-k) check bits.
(which are the remainder bits)

• Output polynomial in the form:

T(x) = xn-k . B(x) + R(x)
( Note : n - k = r = degree of generator polynomial )
94
 Encoding Circuit
Gate

g1 g2 gn-k-1

r0 r1 rn-k-1 +

N-k Shift Register Stages V(x)

B(x) Out

• For the first k shifts, the Gate and Switch are at the ON
position. The k information bits are shifted into the register
and to the output simultaneously.

• For the remaining n - k shifts, the Gate and Switch are turned to
OFF position. The (n-k) check bits (remainder bits) in the
registers are shifted to the output.

95
 Encoding Circuit
• Example: Encoding a (7,4) code
Let G(x) = x3 + x + 1
B(x) = x3 + x2 + 1 (B = 1101)
Gate Clock
Input Register Out
Cycle
0 0 0 0 0
0 1 2 1 1 1 1 0 1
x x x +
2 1 1 0 1 1
Out 3 0 1 0 0 0
Input (1001011)
(1011(M)) 4 1 1 0 0 1
5 0 1 0 0
6 0 0 1 0
7 0 0 0 1
96
Alternative Encoding Circuit

97
 Alternative Encoding Circuit
G(x) = ? Gate

Code Word = (M)11100110 0110(L)

98
Alternative Encoding Circuit

FCS SR

Receive SR

99
 Exercise
• Given the following polynomial divisor circuit, derive
the corresponding generator polynomial G(x).
• Verify that the above circuit produces maximum
sequence as it is clocked, for any pre-loaded bit
patterns except 0000.
• Assuming an incoming code-word T ’ = 10110110,
show the outcome of the error detection process
with a step-by-step shift of the incoming bit string
(MSB first).

Input Output

100
 M-out-of-N Code
• An m-out-of-n code: with a code word length of n
bits, each valid code word contains exactly m 1s and
n-m 0s
• A single bit error will cause the code word to have
either m + 1 or m – 1 1s

101
 3-out-of-6 Code
• The simplest implementation is to append a string of
1s to the original data until it contains m 1s, then
append 0s to create a code of length n.
Original 3 Data Bits Appended Bits
0 0 0 1 1 1
0 0 1 1 1 0
0 1 0 1 1 0
0 1 1 1 0 0
1 0 0 1 1 0
1 0 1 1 0 0
1 1 0 1 0 0
1 1 1 0 0 0

102
 2-out-of-5 Code
• Ten possible combinations
with two 1s in a five-bit code Digit Telecomm. POSTNET
01236 74210
word.
0 01100 11000
• Popular for representing
1 11000 00011
decimal digits
• A weighted code. There are 2 10100 00101
different ways to assign 3 10010 00110
weights to each bit so that 4 01010 01001
the sum is the desired value, 5 00110 01010
with an exception for 0. 6 10001 01100
7 01001 10001
8 00101 10010
9 00011 10100

103
 Checker for M-out-of-N Code
• For valid m-out-of-n code inputs, the checker’s
output is 01 or 10
• If the number of 1s at the input is greater or less than
m (invalid code inputs), the output is 11 or 00
• Code words contain the same numbers of 1s and 0s,
i.e. n=2m. Code of this type are known as k -out-of-
2k codes

104
 Checker for k-out-of-2k Code
• The 2k bits are partitioned into two disjoint subsets
A & B:
A(x1, x2, x3, …, xk) & B(xk+1, xk+2, xk+3, …, x2k)

• Outputs of the checker are Z1 & Z2

(i =1,3,5,…. an odd number)

(i =0,2,4…. an even number)

kA & kB are the number of 1s occurring in subsets A&B

105
 Checker for k-out-of-2k Code
• T(kAi) Represents the function which has the value
1 if and only if the number of 1s in A is greater than
or equal to the value i

• T(kB k-i) Represents the function which has the

value 1 if and only if the number of 1s in B is greater
than or equal to the value k-i

106
 Example
• Design a totally self-checking 2-out-of-4 checker:
k=2, A=(x1,x2) & B=(x3,x4)

= x3 x4 + x 1 x2

107
 Example
• Design a totally self-checking 3-out-of-6 checker:
k=3, A=(x1,x2,x3) & B=(x4,x5,x6)

108
 M-out-of-N Checker
• A general m-out-of-n checker, where n≠2m, can be
realized by translating the given code to a 1-out-of-
𝑪𝒏𝒎 code, which is converted to a k-out-of-2k code via
a totally self-checking translator

109
 Example
• Design a 2-out-of-5 code checker

110
 Example
• Design steps
– Changing the 2-out-of-5 code into a 1-out-of-10 code
– Translating the 1-out-of-10 code into a 3-out-of-6 code
– Design a 3-out-of-6 checker

111
 Example
• Design steps
– 1st Step: Changing the 2-out-of-5 code into a 1-out-of-10
code
– 2nd Step: Translating the 1-out-of-10 code into a 3-out-of-6
code
– 3rd Step: Design a 3-out-of-6 checker

112
 Example
• 1st step: Decoding the 2-out-of-5 code into the 1-out-
of-10 code
– Truth table for 2-out-of-5 to 1-out-of-10 decoder

113
 Example
• 1st step: Decoding the 2-out-of-5 code into the 1-out-
of-10 code
– 2-out-of-5 to 1-out-of-10 decoder

114
 Example
• 2nd step: translate the 1-out-of-10 code into a 3-out-
of-6 code
– Truth table for 1-out-of-10 to 3-out-of-6 translator

115
 Example
• 2nd step: translate the 1-out-of-10 code into a 3-out-
of-6 code
– 1-out-of-10 to 3-out-of-6 translator

• 3rd step: design a 3-out-of-6 checker

116
 SUMMARY:
DATA CODING
• Secure digital data transmission can be achieved by
error detection/correction codes.
• Error detection/correction codes are implemented
through additional bit(s) appended.
• Error detection codes include
– Parity Check, Cyclic Redundancy Check (CRC) , M-Out-Of-
N codes and Cryptographic Hash Function
• Error correction codes include
– Repetition code, 2-D Parity Check, Hamming codes, Reed-
Solomon code, Turbo code, and Low Density Parity Check
code (LDPC)
• Shannon’s theorem for fundamental knowledge

117