Dublin City University



[pic]

EE201: Digital Circuits and Systems

Section 2 – Computer Codes

2.1 Binary Coded Decimal (BCD):

Definition

• Widely used representation of numerical data in which each digit of a decimal number is represented by a 4-bit binary number

• For N-digit decimal numbers, their BCD representations require 4 * N bits

Example

• 2 5 9

• 0010 0101 1001

Decimal to BCD Encoder

• 10 inputs and 4 outputs

• Homework: Implement the encoder using gates

BCD to Decimal Decoder

• 4 inputs and 10 outputs

• Homework: Implement the decoder using gates

2.2 Text Coding

Characters

o General term used for letters, digits and punctuation

o Each character is assigned a unique numerical code

o How many codes are needed?

o Digits (10): 0, 1, 2, 3,…, 9

o Lower case letters (26): a, b, c,…, z

o Upper case letters (26): A, B, C,…, Z

o Punctuation (16): . , ; : ? ! “ ‘ ` { } [ ] ( )

o Special characters (18): # $ € ¥ £ % ^ & * + - = \ / < > | ~

o Other characters: § © ® ¶ ± ¢ ¼

o Characters for other languages: ß â ç ê ţ Њ љ Ω פּ

ASCII code

o 7 bits allocated to store each code

o 27 = 128 codes for 128 possible characters

o Covers digits, lower and upper case letters, punctuation, special and other characters

o Does not cover characters for other languages (accents, umlauts, fadas)

0 1 2 3 4 5 6 7 8 9 A B C D E F

0 NUL SOH STX ETX EOT ENQ ACK BEL BS HT LF VT FF CR SO SI

1 DLE DC1 DC2 DC3 DC4 NAK SYN ETB CAN EM SUB ESC FS GS RS US

2 SP ! " # $ % & ' ( ) * + , - . /

3 0 1 2 3 4 5 6 7 8 9 : ; < = > ?

4 @ A B C D E F G H I J K L M N O

5 P Q R S T U V W X Y Z [ \ ] ^ _

6 ` a b c d e f g h i j k l m n o

7 p q r s t u v w x y z { | } ~ DEL

Extended ASCII

o Specified by International Standards Organization-ISO

o A subset of ISO-8859 that includes several sets of characters for writing in Cyrillic, Arabic, Hebrew, etc.

o Extends ASCII, including additional characters used in some West European languages such as Irish, French and German

o One byte (8 bits) allocated to store each code

o 28 = 256 codes for 256 possible characters

o Text encoded in Extended ASCII can be transmitted through e-mail and be printed on any computer system, being accepted as basis for every text file formats

o E.g. ‘a’ 9710 = 11000012 = 6116

|Decimal | | | | | | |9 |7 |

|Binary |0 |1 |1 |0 |0 |0 |0 |1 |

|Hexadecimal | | | |6 | | | |1 |

[pic]

Words (Strings)

o A word is represented as a sequence of 0 or more characters in form of a string or an array of characters

o E.g. “ee201” = [‘e’, ‘e’, ‘2’, ‘0’, ‘1’] ASCII = [101, 101, 50, 48, 49] 10 = [65, 65, 32, 30, 31] 16

|Binary |0 |1 |1 |0 |0 |1 |0 |

▪

• Odd Parity

The parity bit is such set that the total number of bits equal to ‘1’ in the sequence is odd

e.g.:

|1 |0 |1 |0 |1 |0 |0 |0 |

Examples

• Even Parity

o E.g. ‘a’ 9710 = 11000012

|ASCII Decimal | | | | | | |9 |7 |

|ASCII Binary | |1 |1 |0 |0 |0 |0 |1 |

|ASCII Hexa | | | |6 | | | |1 |

|Even Parity Code |1 |1 |1 |0 |0 |0 |0 |1 |

|Even Parity Code Hex | | | |E | | | |1 |

o E.g. 1110100111000012

|Binary | |1 |1 |1 |0 |1 |0 |0 |

|ASCII Binary | |1 |1 |0 |0 |0 |0 |1 |

|ASCII Hex | | | |6 | | | |1 |

|Even Parity Code |0 |1 |1 |0 |0 |0 |0 |1 |

|Even Parity Code Hex | | | |6 | | | |1 |

Application

• Transmission Error Detection

[pic]

• Notes:

o Using a single parity bit, errors in transmission of binary data sequences (words) can be detected

o Only singular errors can be detected (errors that affect only one bit) or multiple errors if odd number of bits are affected

o This setup cannot detect where the error takes place and therefore it cannot be corrected

• Error Correction:

o Using a matrix-like setup that makes use of two sets of parity bits: on each word and on corresponding bits from the run of words respectively can detect and correct singular errors

2.5 Hamming Code:

Motivation

Hamming code enables single errors to be detected and corrected

Description

• Employs P parity bits for M data bits, where:

• Parity bits are placed in positions power of 2, between data bits:

P1, P2, P4, P8, P16, …

• Each parity bit checks those data bits located in positions that, expressed in binary, have ‘1’-s on columns that correspond to that parity bit

• Therefore parity bits check the following:

P1 -> P1, D3, D5, D7, D9, …

P2 -> P2, D3, D6, D7, D10, D11, …

P4 -> P4, D5, D6, D7, D12, D13, D14, D15, …

P8 -> P8, D9, D10, D11, D12, D13, D14, D15, …

Encoding and Transmission

• Count number of data bits: M

• Determine number of parity bits P, such as:

[pic]

• For each of the P parity bits list the data bits checked by it and determine its value based on the values of the data bits and of the even or odd parity used

• Place the parity bits between data bits in their locations forming a Hamming coded sequence:

P1, P2, D3, P4, D5, D6, D7, P8, D9, D10, D11, …

• Transmit the Hamming coded sequence of bits

Detection and Correction

• Compute the number of correction bits P given N the length of the Hamming coded sequence, such as:

[pic]

• Compute the value of the correction bits taking into account the fact that even or odd parity is employed

• Each correction bit checks the same bits from the code as the parity bits used during encoding

C1 -> P1, D3, D5, D7, D9, …

C2 -> P2, D3, D6, D7, D10, D11, …

C4 -> P4, D5, D6, D7, D12, D13, D14, D15, …

C8 -> P8, D9, D10, D11, D12, D13, D14, D15, …

…

• Computes the detection code:

… C8 C4 C2 C1

• This code expressed in binary indicates the position of the bit affected by an eventual singular error and can be used for the correction

• Correction is performed by inverting the value of the error bit

• Extract original data

Example

Encoding and Transmission

• Data bits: 1010

• Count number of data bits: M = 4

• Number of parity bits P = 3, such as:

[pic]

• Hamming coded sequence:

|P1 |P2 |D3 |P4 |D5 |D6 |D7 |

| | |1 | |0 |1 |0 |

•

• Compute the P parity bits based on even parity:

P1 -> P1, D3, D5, D7 P1, 1, 0, 0 => P1 = 1

P2 -> P2, D3, D6, D7 P2, 1, 1, 0 => P2 = 0

P4 -> P4, D5, D6, D7 P4, 0, 1, 0 => P4 = 1

• Place the parity bits between data bits in their locations forming a Hamming coded sequence:

|P1 |P2 |D3 |P4 |D5 |D6 |D7 |

|1 |0 |1 |1 |0 |1 |0 |

• Transmit the Hamming coded sequence of bits

Error Detection and Correction

• Assume received code: 1001010

|P1 |P2 |D3 |P4 |D5 |D6 |D7 |

|1 |0 |0 |1 |0 |1 |0 |

• Length of the Hamming coded sequence N = 7

• Number of correction bits: P = 3, such as:

[pic]

• Compute the value of the correction bits taking into account the even parity used:

C1 -> P1, D3, D5, D7 1, 0, 0, 0 => C1 = 1

C2 -> P2, D3, D6, D7 0, 0, 1, 0 => C2 = 1

C4 -> P4, D5, D6, D7 1, 0, 1, 0 => C4 = 0

• Computes the detection code:

C4 C2 C1 0 1 1 2 = 3 10 => Error bit D3

• Perform the correction by inverting the value of the error bit

D3 = 1

• Extract the original data:

D3 D5 D6 D7 1 0 1 0

Implementation

[pic]

-----------------------

|Decimal |BCD |

|N |B0 |B1 |B2 |B3 |

|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 |

|S0 |S1 |

|N |G0 |G1 |G2 |G3 |

|0 |0 |0 |0 |0 |

|1 |0 |0 |0 |1 |

|2 |0 |0 |1 |1 |

|3 |0 |0 |1 |0 |

|4 |0 |1 |1 |0 |

|5 |0 |1 |1 |1 |

|6 |0 |1 |0 |1 |

|7 |0 |1 |0 |0 |

|8 |1 |1 |0 |0 |

|9 |1 |1 |0 |1 |

|10 |1 |1 |1 |1 |

|11 |1 |1 |1 |0 |

|12 |1 |0 |1 |0 |

|13 |1 |0 |1 |1 |

|14 |1 |0 |0 |1 |

|15 |1 |0 |0 |0 |

Even parity bit

|Inputs |Outputs |

|B0 |B1 |

|B0 |B1 |B2 |B3 |G0 |G1 |G2 |G3 |

|0 |0 |0 |0 |0 |0 |0 |0 |

|0 |0 |0 |1 |0 |0 |0 |1 |

|0 |0 |1 |0 |0 |0 |1 |1 |

|0 |0 |1 |1 |0 |0 |1 |0 |

|0 |1 |0 |0 |0 |1 |1 |0 |

|0 |1 |0 |1 |0 |1 |1 |1 |

|0 |1 |1 |0 |0 |1 |0 |1 |

|0 |1 |1 |1 |0 |1 |0 |0 |

|1 |0 |0 |0 |1 |1 |0 |0 |

|1 |0 |0 |1 |1 |1 |0 |1 |

|1 |0 |1 |0 |1 |1 |1 |1 |

|1 |0 |1 |1 |1 |1 |1 |0 |

|1 |1 |0 |0 |1 |0 |1 |0 |

|1 |1 |0 |1 |1 |0 |1 |1 |

|1 |1 |1 |0 |1 |0 |0 |1 |

|1 |1 |1 |1 |1 |0 |0 |0 |

|C8 |C4 |C2 |C1 |Error bit |

|0 |0 |0 |0 |None |

|0 |0 |0 |1 |P1 |

|0 |0 |1 |0 |P2 |

|0 |0 |1 |1 |D3 |

|0 |1 |0 |0 |P4 |

|0 |1 |0 |1 |D5 |

|0 |1 |1 |0 |D6 |

|0 |1 |1 |1 |D7 |

|1 |0 |0 |0 |P8 |

|1 |0 |0 |1 |D9 |

|1 |0 |1 |0 |D10 |

[pic]

|Bit position |8 |4 |[pic][?]()*EGgh|1 |Parity bit |

| | | |tuòóô> F ` a x | | |

| | | |y | | |

| | | |ðÜðλΨ˜‰‰p‰aI‰| | |

| | | |‰E‰h±Eî.jh±EîCJ| | |

| | | |OJ[?]QJ[?]U[pic| | |

| | | |]^J[?]mHnHsH | | |

| | | |u[pic]h±Eî5?CJO| | |

| | | |J[?]QJ[?]\?^J[?| | |

| | | |]h±Eî5?CJOJ[?]Q| | |

| | | |J[?]\?^J[?]h±Eî| | |

| | | |OJ[?]QJ[?]^J[?]| | |

| | | |h±Eî5?CJ$OJ[?]Q| | |

| | | |J[?]\?^J[?]h±Eî| | |

| | | |5?>*[pic]CJ(OJ[| | |

| | | |?]QJ[?]\?^J[?]$| | |

| | | |h±Eî5?CJ(OJ[?]Q| | |

| | | |J[?]\?^J[?]mH | | |

| | | |sH | | |

| | | |$h±Eî5?CJ0OJ[?]| | |

| | | |QJ[?]\?^J[?]mH | | |

| | | |sH | | |

| | | |h±EîOJ[?]QJ[?]^| | |

| | | |J[?]mH sH | | |

| | | |'jh±EîCJ0OJ[?]Q| | |

| | | |J[?]2 | | |

|1 |0 |0 |0 |1 |P1 |

|2 |0 |0 |1 |0 |P2 |

|3 |0 |0 |1 |1 |P1, P2 |

|4 |0 |1 |0 |0 |P4 |

|5 |0 |1 |0 |1 |P1, P4 |

|6 |0 |1 |1 |0 |P2, P4 |

|7 |0 |1 |1 |1 |P1, P2, P4 |

|8 |1 |0 |0 |0 |P8 |

|9 |1 |0 |0 |1 |P1, P8 |

|10 |1 |0 |1 |0 |P2, P8 |

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download