18 entry daha
  • ufak veriler için hesaplaması pek zevkli hata sezme* algoritması.
    0'lar ve 1'lerden oluşan veri bloğu, bir polinom şeklinde yazılır (p(x)). ardından, derecesi p olan bir g(x) polinomu seçilir. bu g(x) polinomu belirli standartlara uygun olarak belirlenmiş birtakım asal polinomlardan biridir.
    p(x) polinomu, x^p ile genişletilir (p=g(x) polinomunun derecesi). oluşan bu polinomun, g(x) polinomuna bölümünden kalana r(x) polinomu denir. bu r(x) polinomunu ifade eden, 1 ve 0'lardan oluşan veri bloğu, göndermek istediğimiz veri bloğunun sonuna eklenir. oluşan veri bloğu t(x) adında bir polinomla ifade edilir.
    alıcının aldığı veriyi ifade eden polinom, s(x) polinomu olarak ifade edilir. bu s(x) polinomu, alıcı-verici arasında ortaklaşa belirlenmiş olan g(x) polinomuna bölünür ve bu bölümden kalan polinom e(x) adıyla anılır. e(x)'in sıfırdan farklı olduğu durumlarda, alınan veri hatalıdır denir. çoğunlukla e(x)=0 olan durumlarda veri doğru alınmıştır fakat veri yanlış alındığı halde e(x)=0 çıkabilir.

    örneğin, 1101101011 şeklinde bir veri bloğunu göndermek istiyoruz diyelim. bu veri bloğunu ifade eden p(x)=x^9+x^8+x^6+x^5+x^3+x+1 olacaktır. bu veri bloğu için kullanacağımız üreteç polinom g(x), önceden belirlenmiş birtakım polinomlar arasından seçtiğimiz x^4+x^2+x+1 polinomu olsun. p=4 olduğundan, x^p = x^4 olacaktır. p(x) polinomu x^4 ile genişletildiğinde x^13+x^12+x^10+x^9+x^7+x^5+x^4 polinomunu elde edilir.
    bu polinomu g(x) polinomuna böldüğümüzde elde ettiğimiz kalan polinom, yani r(x)=x^2+x olacaktır (bkz: polinom bölmesi). r(x)'in ifade ettiği 4 bitlik veri bloğu: 0110'dır (bkz: crc katarı).
    t(x)=x^p.p(x)+r(x) 'ten; t(x) = (x^4)(x^9+x^8+x^6+x^5+x^3+x+1) + (x^2+x) olacak; gönderilecek veri bloğu "11011010110110" olacaktır.
    alıcının bu veri bloğunu hatalı olarak aldığını farzedelim. bu hatalı veri bloğu "11010110110110" olsun. yani, s(x)=x^13+x^12+x^10+x^8+x^7+x^5+x^4+x^2+x .
    alıcı bu s(x) polinomunu, g(x)=x^4+x^2+x+1 polinomuna böldüğünde, e(x)=1 kalan polinomunu elde edecektir. yani e(x) != 0'dır ve dolayısı ile, veri hatalı gelmiş demektir.

    p=g(x)'in derecesi olmak üzere, birbirinden en uzak hatalı bitler (ilk hatalı bit ile son hatalı bit) arasındaki uzaklık p veya p'den küçük ise hata sezilebilir; aksi durumda sezilemez.
    d: doğru bitleri, y: hatalı bitleri göstermek üzere ve p=4 için: dyyyddyddyyyydd
    bu örnekte birbirlerinden en uzak bitler, 2. ve 13. bitlerdir. aralarındaki uzaklık 10 bit olduğundan, bu verideki hata sezilemez.

    dip not: tüm polinom işlemleri ikilik tabanda gerçekleştirilir.
11 entry daha
hesabın var mı? giriş yap