DV & IIS Lab.

Data and Error

Department of Cyber Security

Ajou University
Manpyo Hong
DATA Representation

• Data Type

• Fixed point representation

• Floating point representation

• Other codes

• Error detection codes

DV & IIS Lab. 2

Information Representation

▪ Fact / Data / Knowledge : code

▪ Data Type
▪ Character
▪ English and western European language : ASCII

▪ Korean etc. : UTF-n and n byte-code

▪ Number
▪ Integer

▪ Real

▪ Complex

▪ Image / sound and video

▪ program

DV & IIS Lab. 3

Abstraction-Software

5V

3.5V 1

1.5V
0V
0

AF0$GR00128
00000R4062K

1110100001100011010000110000 1110100000

000000000000000000 1110100000

DV & IIS Lab. 4

Representation of Text
▪ ANSI’s ASCII
• 8 bit code for English alphabet and numerics and special
characters
▪ UNICODE and UTF-n
▪ More bits are required for multilingual communication
▪ Variable length encoding
▪ Up to 21 bits to represent each symbol

DV & IIS Lab. 5

Binary system

• Number system

anan-1 . . . a1a0. an+1an+2 . . . an+k-1an+k

anbn + an-1bn-1 + . . . + a1b1 + a0b0 + an+1b-1 + an+2b-2. . . + an+k-1b1 + an+kb0

• Conversion decimal to binary, vice versa

Binary to hexa-decimal
Binary to octal.

• Binary operation :
addition/subtraction/multiplication/division

6
Binary Integer System

• Fixed point system

0 1 n-1
S Fraction

Signed-magnitude 1’s complement 2’s complement

000 +0 +0 +0
001 +1 +1 +1
010 +2 +2 +2
011 +3 +3 +3
100 -0 -3 -4
101 -1 -2 -3
110 -2 -1 -2
111 -3 -0 -1

7
Why 2’s complement?

• Conversion 1’s complement to 2’s complement, vice versa

• Binary addition
• Why 2’s complement?
• Subtraction is replaced by addition
• Only one zero
• Additional addition is not required
• Wider range
• Sign extension

8
Binary Real Number system

• Floating point system

0 1 k 1 n-1

S Exponent(E) Mantissa(M)

(-1) SbEM where b is base number and 0.5<= M < 1

• Normalization
• The leftmost position of mantissa contains non-zero digits.

• Issue
• How to represent real zero?
• As k grows, what happened? Wider range
• As n grows, what happened? More accurate precision

9
Truncation error – range problem

• Range problem
0 1 n-1
S Fraction

• Signed-magnitude -(2n-1-1) ~ (2n-1-1)

• 1’s complement -(2n-1-1) ~ (2n-1-1)
• 2’s complement -(2n-1) ~ (2n-1-1)

• Overflow occurs,
when ao’b0’c0 + a0b0c0’
A = a0a1 . . . an-2an-1
B = b0b1 . . . bn-2bn-1. where, a0, b0 is sign
Truncation error – precision problem

• If mantissa size n is 4 and exponent size k is 2,

5
28 = 2.62510 -> 10.1012 1 is truncated

0 1 0 1 0 1 0

1 1 1 5 1 • Truncation error occurs

• 22 + 8
+ 8
= 28 + 8

•
𝟏
+
𝟏
+ 2𝟐 =
𝟏 𝟏
+2
𝟏 • Truncation error dose not occurs
𝟖 𝟖 𝟒 𝟐

11
Truncation error – base conversion

1 • •
• is converted 0.000112
10 10

0.1 = 0.abcdefghijk
0.2 = 0.bcdefghijk a=0
0.4 = 0b.cdefghijk b=0
0.8 = 00c.defghijk c=0
1.6 = 0001.efghijk d=1
0.6 = 0.efghijk
1.2 = e.fghijk e=1
0.2 = 0.fghijk f = b, g = c, h = d, i = e

12
Grey code

Grey code Conversely

gi = bi + bi+1 for i = 0, …, n-2 bn-1 = gn-1

gn-1 = gn-1 bi = gi + bi+1 for i = 0, …, n-2

Hexa GREY code Binary code Hexa GREY code Binary code
0 0000 0000 8 1100 1000
1 0001 0001 9 1101 1001
2 0011 0010 A 1111 1010
3 0010 0011 B 1110 1011
4 0110 0100 C 1010 1100
5 0111 0101 D 1011 1101
6 0101 0110 E 1001 1110
7 0100 0111 F 1000 1111

13
Grey code counter

• Gray code counter

- generate timing sequence of control
- remove the ambiguity during the change from one state of the
counter to the next because only one bit change during the state
transition

14
Other codes

• BCD Code (8421 code)

di = bi3bi2bi1bi0. (where, bij = 0 or 1)

• 2421 code
1101 = 2*1 + 4*1 + 2*0 + 1*1

• Two-out-of-five code
- 3 zeros and two ones. 5! / (3! * 2!).
- single error detection
- waste storage

15
Other codes

• Excess 3 code
- BCD + 0011
- decimal carry generation

• weighted code : each position does have fixed weight

• self complement code : 2421 code, Excess 3 code

16
Self-complement codes

17
Communication errors

sender receiver

- May be damaged during transmission

- Prone to be erroneous
- Detection and correction is needed

▪ Error detection code

▪ Parity bit
▪ Odd and even parity
▪ Checksum and CRC

▪ Error correction code

18
Error Detection code

▪ Question.

What is the probability that an error cannot be detected when n

(even) bits including parity bits are transmitted, assuming that the
probability of changing when one bit is transmitted is λ?

19
Checksum

0x31 0x27 0x4F 0x61

0011 0001 0010 0111 0100 1111 0110 0001
49 + 39 + 79 + 97 = 274
100001000
checksum
0x108
checkbyte 0x0F8

0011 0001 0010 0111 0100 1111 0110 0001 1111 1000

0x108 + 0xF8 = 0x100

20
CRC

▪ Cycle Redundancy Checks

21
CRC

22
CRC

23
Error correction code
Error Correction code by Hamming

▪ Data size : n bits (x0, … , xn-1)

▪ Redundant code size : k bits (c0, … , ck)

▪ n + k + 1 <= 2k

n=4 c0 c1 x0 c2 x1 x2 x3
c2 0 0 0 0 1 1 1 1
c1 0 0 1 1 0 0 1 1
c0 0 1 0 1 0 1 0 1

c0 = x0⊕x1⊕x3
c1 = x0⊕x2⊕x3
c2 = x1⊕x2⊕x3

25
Error Correction code
▪ Message sent : 7(4+3) bits (x0, x1, x2, x3, c0, c1, c2)

▪ Message received : (x0*,x1*,x2* ,x3* ,c0* ,c1* ,c2*)

▪ ECC
c0+ = x0*⊕ x1*⊕ x3*
c1+ = X0* ⊕ x2*⊕ x3*
c2+ = X1* ⊕ x2*⊕ x3*

▪ Error vector E = (e0, e1, e2)

e0 = c0+ ⊕ c0*
e1 = c1+ ⊕ c1*
e2 = c2+ ⊕ c2*

26