error control

KONTROL KONTROL KESALAHANKESALAHAN

((ERROR CONTROL)ERROR CONTROL)

KONTROL KONTROL KESALAHANKESALAHAN

((ERROR CONTROL)ERROR CONTROL)

Agus NursikuwagusAgus Nursikuwagus

Week - XIIWeek - XII

Agus NursikuwagusJaringan Komputer

Teknik Kontrol Kesalahan

• Parity bit• Kode Hamming(Hamming Code)• Go-Back-N• Selective Repeat ARQ


Parity Bit (1)• Parity bit adalah dijit biner yang mengindikasikan

sejumlah bit dengan nilai bit 1 yang diberikan pada untaian bit yang menyatakan apakah even atau odd dari untaian bit tersebut.

• Parity bit digunakan sebagai kode pendeteksian kesalahan sederhana.

• Dua tipe parity :– even parity bit : nilai bit parity akan diset

menjadi 1 jika jumlah bit 1 tersebut ganjil (total bit 1 pada deretan). Contoh yang sering digunakan adalah cyclic redundancy check (CRC), dimana 1 bit CRC dibangkitkan dengan polynomial x+1.

– odd parity bit : nilai bit parity akan diset menjadi 1 jika jumlahbit 1 tersebut adalah genap (total bit 1 pada deretan).


Parity Bit (2)• Cara pendeteksian error :

– Jika bit sejumlah ganjil (termasuk parity bit) berubah dalam suatu transmisi dari untaian bit, maka parity bit menjadi tidak benar, dan dapat dikatakan adanya error ketika transmisi.

– Parity bit merupakan kode pendeteksian error, bukan suatu koreksi kode sehingga tidak bisa menentukan bagian bit yang corrupt.

– Kalau terjadi hal demikian maka harus dikirim kembali data tersebut.

• Parity bit memiliki kelebihan yaitu dengan menggunakan bit tunggal untuk mendeteksi adanya error dengan membangkitkan gerbang XOR.


Parity Bit (3)• Parity memiliki keterbatasan dalam hal skema. • Parity bit hanya menjamin pendeteksian untuk bit

berjumlah ganjil. Sedangkan jika bit berjumlah genap terjadi error, parity bit akan tetap mencatat sebagai hal yang benar walaupun data tersebut corrupt.

• Contoh : dikirimkan data sejumlah 4 bit 1001A computes even parity: 1^0^0^1 = 0 A sends: 01001 B receives: 01001 B validates even parity: 1^0^0^1 = 0 A computes odd parity: ~(1^0^0^1) = 1 A sends: 11001B receives: 11001 B validates odd parity: ~(1^0^0^1) = 1


Parity Bit (4)• Contoh :• Asumsi even parity, dikirimkan 4 bit dengan nilai 0010

(parity bit berada pada sisi kiri bit yang dikirim/diterima) :

A computes even parity: 0^0^1^0 = 1 A sends: 10010 *** TRANSMISSION ERROR *** B receives: 11010 B validates even parity: 1^0^1^0 = 0

• B menghitung nilai parity (0) yang tidak sama dengan parity bit (1) pada nilai bit yang diterima, yang mengindikasikan adanya bit error.

• Hal yang sama (even parity, value 0010) , parity bit mendapatkan bit corrupt juga :

A computes even parity: 0^0^1^0 = 1 A sends: 10010 *** TRANSMISSION ERROR *** B receives: 00010 B validates even parity: 0^0^1^0 = 1


Parity Bit (5)• Penggunaan Parity Bit :

– SCSI– Microprosesor– Main Memory

• Pada transmisi data, lebar bit yang sering digunakan adalah 7 bit , even parity, dan dua atau satu bit stop.

• Pada komunikasi serial, parity juga dipakai pada UART.


Parity Bit (6)


Kode Hamming (1)• Pada telekomunikasi, kode hamming merupakan

kode pengkoreksian kesalahan linear yang ditemukan oleh Richard Hamming.

• Kode hamming dapat mendeteksi dan memperbaiki kesalahan pada singke bit.

• Dapat mendeteksi kesalahan double bit tetapi tidak memperbaiki.

• Dapat dikatakan juga bahwa Hamming distance antara transmit dan receive harus Nol (0).

• Jelasnya kode parity sederhana tidak dapat mendeteksi kesalahan dimana dua bit ditransposkan begitupun juga tidak dapat memperbaiki kesalahan walaupun ditemukan.


Kode Hamming (2)• Pada terminologi matematika, kode hamming

merupakan kelas dari kode biner linear. • Untuk setiap nilai integer m > 1, memiliki kode

dengan parameter [2m − 1,2m − m − 1,3]. • Matrik Parity-Check kode Hamming dibangun

pada daftar semua kolom dengan panjang m yang berpasangan secara bebas.

• Jika ada banyak pengkoreksian kesalahan termasuk pada suatu pesan, dan jika setiap bit dapat ditata untuk setiap kesalahan yang berbeda yang menghasilkan hasil error yang berbeda, maka bit buruk dapat diidentifikasi.

• Dalam pesan yang memuat 7 bit, ada tujuh kemungkinan single bit error, maka tiga bit kontrol error dapat secara potensial menspesifikasikan error yang terjadi tetapi juga mencari bit penyebab terjadinya kesalahan.


Kode Hamming (3)• Algoritma umum :

– Semua posisi bit merupakan (posisi 1, 2, 4, 8, 16, 32, 64, etc.),

– Posisi bit lainnya pada data juga dikodekan (posisi 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, etc.),

– Setiap parity bit mengkalkulasi untuk bit pada kode word.– Posisi bit akan menentukan unrutan bit yang dicek atau

skip. • Position 1 (n=1): skip 0 bit (0=n-1), check 1 bit (n), skip 1 bit (n),

check 1 bit (n), skip 1 bit (n), etc. • Position 2 (n=2): skip 1 bit (1=n-1), check 2 bits (n), skip 2 bits (n),

check 2 bits (n), skip 2 bits (n), etc. • Position 4 (n=4): skip 3 bits (3=n-1), check 4 bits (n), skip 4 bits (n),

check 4 bits (n), skip 4 bits (n), etc. • Position 8 (n=8): skip 7 bits (7=n-1), check 8 bits (n), skip 8 bits (n), check 8 bits

(n), skip 8 bits (n), etc. • Position 16 (n=16): skip 15 bits (15=n-1), check 16 bits (n), skip 16 bits (n),

check 16 bits (n), skip 16 bits (n), etc. • Position 32 (n=32): skip 31 bits (31=n-1), check 32 bits (n), skip 32 bits (n),

check 32 bits (n), skip 32 bits (n), etc. • General rule for position n: skip n-1 bits, check n bits, skip n bits, check n bits... • And so on.


Kode Hamming (3)• Contoh :

– Parity bit pada posisi 2k mencek bit pada posisi yang memiliki himpunan bit sebanyak k.

– bit 13 dalam biner 1101(2), dicek oleh bit 1000(2) = 8, 0100(2)=4 and 0001(2) = 1.


Kode Hamming (4)• Kode hamming dengan parity tambahan.

– Kode hamming memiliki minimum jarak tiga (3), yang artinya kode dapat kesalahan dan memperbaiki single error.

– Hal ini dapat dilakukan dengan menambahkan parity ekstra, sehingga dapat meningkatkan jarak hamming minimal menjadi 4.

– Hal ini memberikan kode yang dapat mendeteksi dan memperbaiki single error, atau mendeteksi double error.

– Secara umum, jika jarak minimum untuk perbaikan kode diberikan W, maka error dapat dideteksi sehingga

dapat diperbaiki.


Kode Hamming (5)• Kode Hamming(7,4)

• Gambar di atas menunjukan 4 data bit dan 3 parity yang diterapkan apda data bit.


Kode Hamming (6)

• Matrik generator G, parity cek H


Kode Hamming (7)• Kode Hamming(8,4)


Kode Hamming (8)• Matrik Parity cek untuk Hamming(8,4)

• Contoh :Bit 1011 dikodekan menjadi 01100110 dimana warna biru merupakan data, dan parity berwarna merah dari kode hamming (7,4); warna hijau merupakan parity tambahan dari hamming (8,4). Dijit berwarna hijau membuat kode even parity (7,4)


Kode Hamming (9)

• Kode Hamming(11,7)


Kode Hamming (10)

Posisi bit pada kode hamming (11,7)

Pemetaan bit posisi. Parity dengan warna merah, kuning, hijau, dan biru merupakan parity even. ,


Kode Hamming (11)

Bit error pada bit 11 disebabkan oleh lingkaran berwarna merah, kuning, hijau.


Kode Hamming (12)

• Anggap 7 bit data "0110101"., untuk menunjukan bagaimana kode hamming dihitung dan digunakan untuk deteksi dan memperbaiki error, boleh dilihat pada tabel berikut.

• d menyatakan data, dan p merupakan parity bitp1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7

Data word (without parity): 0 1 1 0 1 0 1

p1 1 0 1 0 1 1

p2 0 0 1 0 0 1

p3 0 1 1 0

p4 0 1 0 1

Data word (with parity): 1 0 0 0 1 1 0 0 1 0 1

Calculation of Hamming code parity bits


Kode Hamming (13)

• Dari tabel sebelumnya dapat terlihat bahwa data baru "10001100101".

• Diasumsikan bahwa bit terakhir terjadi corrupt dan dikembali dari 1 ke 0.

• Data baru menjadi "10001100100"

p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7Parity check

Parity bit

Received data word:

1 0 0 0 1 1 0 0 1 0 0

p1 1 0 1 0 1 0 Fail 1

p2 0 0 1 0 0 0 Fail 1

p3 0 1 1 0 Pass 0

p4 0 1 0 0 Fail 1

Checking of parity bits (switched bit highlighted)


Kode Hamming (14)p4 p3 p2 p1

Binary 1 0 1 1

Decimal 8 2 1 Σ = 11

•Dengan melipat bit ke-11, merubah kembali 10001100100 menjadi 10001100101.

•Dengan menghapus kode Hamming memberikan data asli 0110101


Kode Hamming (15)Hamming distance

3-bit binary cube for finding hamming distance

Two example distances: 100->011 has distance 3 (red path); 010->111 has distance 2 (blue path)


Kode Hamming (16)

4-bit binary hypercube for finding hamming distance


Kode Hamming (17)

Two example distances: 0100->1001 has distance 3 (red path); 0110->1110 has distance 1 (blue path)


Kode Hamming (18)• Contoh :

– The Hamming distance between 1011101 and 1001001 is 2.

– The Hamming distance between 2143896 and 2233796 is 3.

– The Hamming distance between "toned" and "roses" is 3.


Hamming Codes (19)• Given any two codewords, say, 10001001 and

10110001, it is possible to determine how many corresponding bits differ.

• In this case, 3 bits differ. • To determine how many bits differ, just exclusive OR

the two codewords and count the number of 1 bits in the result, for example:

• The number of bit positions in which two codewords differ is called the Hamming distance (Hamming, 1950)

• Its significance is that if two codewords are a Hamming distance d apart, it will require d single-bit errors to convert one into the other.


Hamming Codes (20)• The error-detecting and error-correcting properties of a

code depend on its Hamming distance detect d errors, you need a distance d + 1 code because with such a code there is no way that d single-bit errors can change a valid codeword into another valid codeword

• When the receiver sees an invalid codeword, it can tell that a transmission error has occurred

• Similarly, to correct d errors, you need a distance 2d + 1 code because that way the legal codewords are so far apart that even with d changes, the original codeword is still closer than any other codeword, so it can be uniquely determined

• As a simple example of an error-detecting code, consider a code in which a single parity bit is appended to the data


Hamming Codes (21)• The parity bit is chosen so that the number of 1 bits in

the codeword is even (or odd). • For example, when 1011010 is sent in even parity, a bit

is added to the end to make it 10110100. With odd parity 1011010 becomes 10110101

• A code with a single parity bit has a distance 2, since any single-bit error produces a codeword with the wrong parity. It can be used to detect single errors

• As a simple example of an error-correcting code, consider a code with only four valid codewords:

0000000000, 0000011111, 1111100000, 1111111111 • This code has a distance 5, which means that it can

correct double errors • If the codeword 0000000111 arrives, the receiver knows

that the original must have been 0000011111. If, however, a triple error changes 0000000000 into 0000000111, the error will not be corrected properly


Hamming Codes (22)• Imagine that we want to design a code with m

message bits and r check bits that will allow all single errors to be corrected.

• Each of the 2m legal messages has n illegal codewords at a distance 1 from it.

• These are formed by systematically inverting each of the n bits in the n-bit codeword formed from it.

• Thus, each of the 2m legal messages requires n + 1 bit patterns dedicated to it.

• Since the total number of bit patterns is 2n, we must have


Hamming Codes (23)• Using n = m + r, this requirement becomes

• Given m, this puts a lower limit on the number of check bits needed to correct single errors.

• This theoretical lower limit can, in fact, be achieved using a method due to Hamming (1950).

• The bits of the codeword are numbered consecutively, starting with bit 1 at the left end, bit 2 to its immediate right, and so on.

• The bits that are powers of 2 (1, 2, 4, 8, 16, etc.) are check bits.


Hamming Codes (24)• The rest (3, 5, 6, 7, 9, etc.) are filled up with the m

data bits.• Each check bit forces the parity of some collection of

bits, including itself, to be even (or odd). • A bit may be included in several parity computations. • To see which check bits the data bit in position k

contributes to, rewrite k as a sum of powers of 2. • For example, 11 = 1 + 2 + 8 and 29 = 1 + 4 + 8 +

16. A bit is checked by just those check bits occurring in its expansion (e.g., bit 11 is checked by bits 1, 2, and 8).


Hamming Codes (25)


Hamming Codes (26)• Hamming codes can only correct single errors. • However, there is a trick that can be used to permit

Hamming codes to correct burst errors. • A sequence of k consecutive codewords are arranged as a

matrix, one codeword per row.• Normally, the data would be transmitted one codeword at a

time, from left to right. • To correct burst errors, the data should be transmitted one

column at a time, starting with the leftmost column. • When all k bits have been sent, the second column is sent,

and so on, as indicated in figure before • When the frame arrives at the receiver, the matrix is

reconstructed, one column at a time. • If a burst error of length k occurs, at most 1 bit in each of the

k codewords will have been affected, but the Hamming code can correct one error per codeword, so the entire block can be restored.

• This method uses kr check bits to make blocks of km data bits immune to a single burst error of length k or less.


Go-Back-N ARQ• Uses sliding-window flow control• When receiver detects error, it sends

negative acknowledgment (REJ)• Sender must begin transmitting

again from rejected frame• Transmitter must keep a copy of all

transmitted frames

error control

Documents