Seri İletişim #2 - Hata Sezme ve Düzeltme Yöntemleri

Yazılım Haberleşme Elektronik | | Barış Çelik<bariscelikweb@gmail.com>

Seri iletişim #1 yazısında seri haberleşmenin temellerinden bahsetmiştim. Bilindiği üzere teori ve pratik çoğunlukla tam anlamıyla birbirine eşit değildir. Pratikteki seri iletişim uygulamalarında verinin aktarılması ve saklanmasında bazı önlemler almak gereklidir. Çünkü gönderilen bitler iletişim esnasında bozulabilir ya da kaybolabilir. Veri, karşı tarafta tasarlanan veri yapısına uygun olması gerektiği için bitlerdeki en küçük bozulma sonucu da bozar.

Bu sorunların üstesinden gelebilmek için hata sezme yöntemleri sıkça kullanılır. Aktarımda ya da depolamada bir hata olduğu anlaşıldığında, karşı taraftan veriyi tekrar göndermesi istenebilir. Fakat; veriyi arşivlerken böyle bir talepte bulunulamaz. Çünkü; veri transfer edilmiş ve haberleşme işlemi bitmiştir. Bu noktadan sonra önemli olan arşivlenmiş verideki hatayı tespit edip onu mümkün olduğunca düzeltmektir. Bu da hata düzeltme yöntemlerine duyulan ihtiyacın kaynağıdır.

Başlıca hata sezme yöntemleri yankılama, parite (eşlik) biti, checksum, boyuna fazlalık sınaması ve en sık kullanılanı CRC’dir.

Yankılama (Echoplex)

Çoğu programcının her gün kullandığı seri terminalleri düşünelim. Aslında klavyeden bir karaktere bastığınızda gördüğünüz sizin girdiniz değil, sistemin size döndüğü çıktıdır. Yani kullanıcı terminale bir karakter transfer eder ve terminal cevap olarak aynı karakteri kullanıcıya gösterir. Bunun sonucunda kullanıcı ekrandaki karakterle klavyede bastığı karakteri karşılaştırarak aktarımın doğruluğunu anlar. Örneğin:

1. a (01100001) karakteri seri porttan gönderilir
2. ana sistem seri porttan cevap verir => a (01100001)
3. gönderilen ve dönen veri aynı olduğu görülür

SONUÇ BAŞARILI

Toplam Tamamlayıcı Checksum

Aktarılan verinin yanına negatifini ekleyip, karşıda ikisini toplama temeline dayanır. Veri, işaretsiz (unsigned) olarak kabul edilir. Peşine verinin ikiye tümleyeni eklenir. Karşı tarafa bu mesaj ulaştığında bu iki parçayı birbiriyle toplar ve sonuçta ‘0’ çıkarsa veri doğru aktarılmıştır.

\[\begin{array} {|r|r|r|r|r|}\hline B_0 & B_1 & ... & B_n & \textsf{CHECKSUM} \\ \hline \end{array} = 0\]

Eşlik (Parite) Biti

Eşlik biti veri yığınındaki tek sayıda (1,3,5,7…) olan bit hatalarını çözmeyi sağlar. Çift eşlik biti uygulamasında, gönderilecek veri içindeki tek sayıda 1 olan bit varsa eşlik biti 1 yoksa 0 olarak gönderilir. Alıcı tarafında yine aynı işlem yapılıp, gelen eşlik bitiyle hesaplanan eşlik biti karşılaştırılarak verinin hatası belirlenir. Tek eşlik biti uygulamasının farkı verideki 1 değerlerinin toplamını çift sayıya tamamlamak yerine tek sayıya tamamlamaktır. ASCII karakter gönderiminde sıklıkla hata sezmek için kullanılır.

\[\begin{array} {|r|r|}\hline 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ \hline \end{array}\]

Bir veri yığınının çift eşlik biti, verinin her bir bitinin toplanıp, 10 tabanında yazılması ve 2’ye bölümünden kalanının bulunmasıyla hesaplanır. Yukarıdaki verinin eşlik bitini hesaplayalım:

\[\begin{align} p_1 &= ((d_1)_{10} + (d_2)_{10} + (d_3)_{10} + (d_4)_{10} + (d_5)_{10} + (d_6)_{10} + (d_7)_{10}) \mod 2_{10}\\ &= \underbrace{(1 + 0 + 0 + 1 + 0 + 1 + 0)}_{\Large \textsf {3}} \mod 2_{10} \\ p_1 &= 1\\ \end{align}\] \[\begin{array} {|r|r|}\hline 1 & 0 & 0 & 1 & 0 & 1 & 0 & \textbf{1}\\ \hline \end{array}\]

Boyuna Fazlalık Sınaması (Longitudinal Redundancy Check)

LRC1, çoklu veri aktarımında, yani veri paketinin birden çok gönderildiği durumda her paketi bir satır olarak kabul edip, hem satırda hem de sütunda eşlik sınaması yapma temeline dayanır. Bu yöntem hem hata sezme, hem de kısmi düzeltme imkanı tanıyabilir.

“HATA” sözcüğünün ASCII (7-bit) karşılığının LRC hesabı şu şekildedir.

\[\left[\begin{array}{cccccccc|c} & \textbf{B1} & \textbf{B2} & \textbf{B3} & \textbf{B4} & \textbf{B5} & \textbf{B6} & \textbf{B7} \\ H & 1 & 0 & 0 & 1 & 0 & 0 & 0 & \textbf{0} \\ A & 1 & 0 & 0 & 0 & 0 & 0 & 1 & \textbf{0} \\ T & 1 & 0 & 1 & 0 & 1 & 0 & 0 & \textbf{1} \\ A & 1 & 0 & 0 & 0 & 0 & 0 & 1 & \textbf{0} \\ & \textbf{0} & \textbf{0} & \textbf{1} & \textbf{1} & \textbf{1} & \textbf{0} & \textbf{0} \end{array}\right]\]

H, A, T, A karakterlerinin ikili karşılığı, sonlarına eşlik bitleri eklenerek, ard arda gönderilmiş ve oluşan matristeki sütunların eşlik bitleri yeni bir satır olarak arkasına eklenmiştir.

Alıcı, eşlik bitlerini hesaplar ve gelen eşlik bitleriyle karşılaştırır. Bir bit bozulursa hem dikey hem de yataydaki eşlik biti yanlış olacaktır. Satır ve sütunun kesiştiği yer bozuk bitin yerini gösterir. Bozuk bit ters çevirilerek düzeltilebilir.

Bu yöntemle sadece aynı satır veya sütundaki tek sayıda hatalı bit sezilebilir. Çünkü; aynı satır ya da sütundaki çift sayıda bitte hata oluştuğunda satır ya da sütun eşlik bitleri de değişeceğinden tüm bozuk bitlerin yeri saptanamaz.

Çevrimli Fazlalık Sınaması (Cyclic Redundancy Check)

CRC yöntemi checksum’un gelişmiş hâlidir ve matematiksel olarak daha karmaşıktır. Sık kullanılan hata sezme yöntemlerinden biridir. Hatta CRC bitlerini hesaplayan iletişim yongaları ve işlemci alt birimleri vardır. Sadece haberleşmede değil, dosya depolamada da kullanılan bir yöntemdir. Bu yöntemde sabit veri bitleri polinom sabitleri olarak gösterilir. Ortaya çıkan polinom, üreteç polinomu denilen çeşitli hata sezme özellikleri bulunan standard polinomlara bölünecektir (Gönderici ve alıcı aynı üreteç polinomu kullanmalıdır). Ancak bundan önce üreteç polinomunun derecesi ile çarpılmalıdır. Çıkan sonuç üreteç polinoma bölündükten sonra, bölme işleminden kalanla toplayıp verinin arkasına eklenerek gönderilir. Böylece veri üreteç fonksiyonun bir katı hâline gelir. Alıcı bit dizisini üreteç polinoma böler. Bölme işleminde kalan “0” ise veri iletimi başarılı demektir.

Özetlersek;

  1. n bitlik bir verinin polinom ifâdesi:

    \[P(x) = \sum_{i=0}^{n-1} b_{i}.x^{i} = b_0.x^0 + b_1.x^1 + ... + b_{n-1}.x^{n-1}\]
  2. \(P(x)\) polinomu \(x^p\) ile çarpılır. Burada p üreteç fonksiyonun derecesini ifâde etmektedir. Bu yaptığımız ikili sistemde bitin arkasına p adet 0 yazmaktır.

    \[x^p.P(x)=x^p.\sum_{i=0}^{n-1} b_{i}.x^{i} = \sum_{i=p}^{p+(n-1)} b_{i}.x^{i} = b_p.x^p + b_{p+1}.x^{p+1} + ... + b_{p+(n-1)}.x^{p+(n-1)}\]
  3. \(x_p.P(x)\) polinomu, \(G(x)\) üreteç polinomuna bölünür. Bazı üreteç polinomları:

    • CRC-3-GSM: \(x^3 + x + 1\)
    • CRC-16-IBM: \(x^{16} + x^{15} + x^2 + 1\)
    • CRC-16-CCITT: \(x^{16} + x^{12} + x^5 + 1\)
  4. Bölme işlemi sonucunda bölüm \(Q(x)\) ve kalan \(R(x)\) olarak ifâde edilirse sonuçta ortaya aşağıdaki eşitlik çıkar:

    \[x^p . P(x) = Q(x) . G(x) + R(x)\]

    Bu ifadeyi düzenlersek

    \[x^p . P(x) - R(x) = Q(x) . G(x)\]

    Modulo 2 aritmetiğinde toplama ve çıkarma aynı işlemdir. Dolayısıyla ifâde şu şekilde de yazılabilir:

    \[x^p . P(x) + R(x) = Q(x) . G(x)\]
  5. İşte alıcıya bu \(Q(x) . G(x)\) çarpımı gönderilir. Alıcı gelen veriyi \(G(x)\)‘e böler, kalan 0 ise bitler bozulmadan gelmiş demektir. Verinin sonundaki p adet üreteç fonksiyona ait bit silinirse geriye verinin kendisi n adet bit olarak kalır.

Örnek

Bir örnekle açıklarsak daha iyi anlaşılabileceğini düşünüyorum.

Göndereceğimiz veri \(\begin{array} {|r|r|}\hline 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ \hline \end{array}\) ,üreteç fonksiyonumuz \(G(x)=x^3+x+1\) (CRC-3-GSM) ,ikili gösterimi \(\begin{array} {|r|r|}\hline 1 & 0 & 1 & 1 \\ \hline \end{array}\)

olsun.

  1. Veriyi polinomla ifâde edelim:

    \[\begin{align} P(X) &= 1 . x^7 + 0 . x^6 + 0 . x^5 + 1 . x^4 + 0 . x^3 + 1 . x^2 + 0 . x^1 + 1 . x^0 \\ &= x^7 + x^4+x^2+1 \end{align}\]
  2. Üreteç polinomumuz 3. dereceden, yani \(p=3\). Veri polinomumuzu \(x^3\) ile çarpalım.

    \[x^3.P(x)=x^{10}+x^7+x^5+x^3\]
  3. Ortaya çıkan \(X^3.P(x)\) polinomunu üreteç fonksiyona bölüp, bölüm ve kalanını bulalım.

    \[\require{enclose} \begin{array}{rl} Q(x) && \\[-3pt] {G(x)} \enclose{longdiv}{x^3.P(x)} \\[-3pt] \end{array} = \begin{array}{rl} x^7+x^5+x^3+x && \\[-3pt] x^3+x+1 \enclose{longdiv}{x^{10}+x^7+x^5+x^3} \\[-3pt] \underline{x^{10}+x^8+x^7\phantom{00000}} \\[-3pt] x^8+x^5+x^3\phantom{000000} \\[-3pt] \underline{x^8+x^6+x^5\phantom{000000}} \\[-3pt] x^6+x^3\phantom{0000000000} \\[-3pt] \underline{x^6+x^4+x^3\phantom{000000}} \\[-3pt] x^4\phantom{000000000000000} \\[-3pt] \underline{x^4+x^2+x\phantom{0000000}} \\[-3pt] x^2+x \phantom{00000000000} \end{array}\]

    Sonuçta:

    \[Q(x) = x^7+x^5+x^3+x \\ R(x) = x^2+x\]

    olarak bulunur.

  4. Gönderilecek bit dizisini yerine koyarsak:

\[\begin{align} Q(x) . G(x)&=x^3 . P(x) + R(x) \\ &= x^{10}+x^7+x^5+x^3+x^2+x \end{align}\]

Polinomu bitlerle ifâde edersek:

\[\underbrace{\begin{array} {|r|r|}\hline 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ \hline \end{array}}_{\Large \textsf {Veri}}\underbrace{\begin{array} {|r|r|}\hline 1 & 1 & 0 \\ \hline \end{array}}_{\Large \textsf {CRC}}\]

Aynı işlemleri bitlerle ifade ederek tekrar yapalım.

1 0 0 1 0 1 0 1  => veri polinomu
1 0 1 1 => üreteç polinomu

1 0 0 1 0 1 0 1   0 0 0 => veri polinomuna üreteç polinomun derecesi kadar (3. dereceden) bit ekleyelim
1 0 1 1                 => üreteç polinoma bölelim, bölme işlemi XOR ile 0 olan değerler kaydırılarak yapılır
---------------------
0 0 1 0 0 1 0 1   0 0 0
    1 0 1 1
-----------------------
0 0 0 0 1 0 0 1   0 0 0
        1 0 1 1   0 0 0
-----------------------
0 0 0 0 0 0 1 0   0 0 0
            1 0   1 1 0
-----------------------
0 0 0 0 0 0 0 0   1 1 0 => kalan (sağ 3 bit)

Gönderilmesi gereken bit dizisi
1 0 0 1 0 1 0 1   1 1 0 => veri polinomu + kalan polinomu

Hata sezme yöntemlerinin tümünde olduğu gibi CRC ile her hata sezilemez. Tek ve çift bit hataların da çözülebildiği polinomlar vardır. Fakat verinin boyutu büyüdükçe hata sezme de zorlaşır. Dolayısıyla tek başına polinom ve CRC yöntemine değil, hesaplanan veri bloklarının boyutu da önemlidir.

Sezilemeyen en temel hata, karşıya \(Q(x) . G(x)\) gönderildiğinde \(Q(x)\) veri polinomunun \(G(x)\) üreteç polinomunun bir katı olması durumudur. Yukarıdaki örneği baz alarak, üreteç fonksiyonun \(G(x) = x^7 + x^4 + x^2 + 1\) olduğunu düşünün. Bu durumda \(Q(x)\), \(G(x)\)‘e tam bölündüğü için \(R(x)\) yani kalan 0 olarak bulunur. Dolayısıyla hata sezilemez.

CRC-3-GSM ile 1 baytlık mesajın CRC bitlerini hesaplayan C/C++ kodu:

#include <stdio.h>
#include <stdint.h>

#define CRC_TO_BINARY(crc)  \
  (crc & 0x04 ? '1' : '0'), \
  (crc & 0x02 ? '1' : '0'), \
  (crc & 0x01 ? '1' : '0')


// shift left crc-3 polynomial (00001011 => 1011000)
// x ^ 3 + x + 1
const uint8_t CRC3_GSM = 0x0B << 4;

uint8_t crc3(uint8_t message)
{

    uint8_t i, crc = 0;

        crc ^= message;
        for (i = 0; i < 8; i++) {

            if (crc & 0x80)
                crc ^= CRC3_GSM;

            crc <<= 1;
        }
        return crc>>5;
}

int main()
{
    uint8_t message = 0x95;

    uint8_t crc = crc3(message);

    printf("CRC3: %d %c%c%c \n", crc, CRC_TO_BINARY(crc));

}

Hamming Kodlaması

CRC ve LRC yöntemlerinde hata oluştuğunda sezip doğru veriyi karşı taraftan isteyerek hatayı onarmaya çalışılmaktadır. Ancak bazı durumlarda bu tek başına yeterli değildir. Örneğin; fazla gecikmenin istenmediği durumda ya da göndericinin tamponunun (buffer) yeterli büyüklükte olmaması, dolayısıyla verinin silinip yenisine yer açılması durumunda veri tekrar istenemez. Dolayısıyla eldeki çevrimdışı veri ile çalışmak gerekir.

Hamming kodu alıcıya ulaşan ve bilinen bir simgeye karşılık olan veri, yolda bir ölçüde bozulmuş bile olsa, alıcının doğru veriyi saptayabilmesini sağlar. Hamming kodlaması verinin peşine tüm kombinasyonlara karşılık düşen eşlik bitinin eklenmesiyle belirlenir. Örneğin; 4 veri biti ve 3 eşlik bitinin olması durumunda Hamming(7,4) adlandırılır, tek bitlik veriyi onarabilir ve şöyle hesaplanır:

\[p_1 = d_1 ⊕ d_2 ⊕ d_4\\ p_2 = d_1 ⊕ d_3 ⊕ d_4\\ p_3 = d_2 ⊕ d_3 ⊕ d_4\]

Burada p eşlik bitlerini, d ise veri bitlerini temsil etmektedir. \(d_1\) bozulduğunda \(p_1\) ve \(p_2\), \(d_2\) bozulduğunda \(p_1\) ve \(p_3\), \(d_3\) bozulduğunda \(p_2\) ve \(p_3\), \(d_4\) bozulduğunda ise \(p_1\), \(p_2\) ve \(p_3\) alıcıya gelen eşlik bitlerinden farklı hesaplanmış olacaktır. Örneğin; gönderilen paket aşağıdaki gibi olsun:

\[\underbrace{\begin{array} {|r|r|}\hline 1 & 1 & 0 & 0\\ \hline \end{array}}_{\Large \textsf {Veri Bitleri}}\underbrace{\begin{array} {|r|r|}\hline 0 & 1 & 1 \\ \hline \end{array}}_{\Large \textsf {Parite Bitleri}}\]

Parite bitleri yukarıdaki gibi hesaplanmıştır. Bu verinin yolda bozulduğunu ve alıcıya aşağıdaki gibi aktarıldığını düşünelim:

\[\underbrace{\begin{array} {|r|r|}\hline 1 & 1 & 1 & 0\\ \hline \end{array}}_{\Large \textsf {Veri Bitleri}}\underbrace{\begin{array} {|r|r|}\hline 0 & 1 & 1 \\ \hline \end{array}}_{\Large \textsf {Parite Bitleri}}\]

Alıcı, veri paketini aldığında Hamming(7,4) kodlamasını uygular.

\[p_1 = 1 ⊕ 1 ⊕ 0 = 0\\ p_2 = 1 ⊕ 1 ⊕ 0 = 0\\ p_3 = 1 ⊕ 1 ⊕ 0 = 0\]

Görüldüğü üzere \(p_2\) ve \(p_3\) yanlıştır. Bu nedenle bozulma 3 numaralı bitte yani \(d_3\)‘tedir. \(d_3\) ters çevirilerek sorun çözülür.