sonBAHAR’ın kodlama dersleri: Bölüm 2

QR Kodları Bölüm 2

Hata Düzeltme Kodları (Error Correction Codes) nasıl oluşturulur?

HELLO WORLD için aşağıdaki veri kod sözcüklerini oluşturmuştuk.
00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 01000000 11101100 00010001 11101100 00010001 11101100 00010001
Ondalık sayılara çevirelim:

32, 91, 11, 120, 209, 114, 220, 77, 67, 64, 236, 17, 236, 17, 236, 17
Bu sayılar mesaj polinom katsayıları. Diğer bir deyişle:
1
(16 terim)
İlk olarak, üreteç polinomu oluşturalım. Bu arkadaşı hata düzeltme seviyesi M, versiyon 1 yani 1-M kodu olarak oluşturalım. Hata düzeltme tablosunda, hata düzeltme kod sözcükleri (error correction codewords) 1-M için 10 adet olmak zorunda. Bir önceki yazımızda bu tablo verilmişti “EC Blok Başına Kod kelimeleri” sütunundan hatırlayın. Peki nasıl hesaplanır bu polinom, bakalım.
Üreteç polinomu kısaca şöyle hesaplanır:
2
Burada unutmamız gereken şu ki Galois Field da çalışırken negatif sayı değerleri pozitif sayı değerleri ile aynıdır yani n=-n dir.  ve unutmayalım α = 2 dir. mesela 2 adet hata düzeltme kod sözcüklerini şu şekilde oluştururuz:
3

ya da

4

şeklinde yazılabilir.
Bu yazım büyük üsler (256 dan büyük) için kolaylık sağlamaktadır.
Eğer büyükse uygulayacağımız işlem şu şekilde olmaktadır, örneğin: 5

olacağından formülümüz şöyle (üs % 256) + tabana yuvarla (üs / 256) not: (% mod işlemi, 256’ya bölümünden kalanı al) (261 % 256) + tabana yuvarla (261 / 256) = (5) +(1.01953125) = (5 + 1) = 6.  (α^256 = α^6)

Biz 2 adet hata düzeltme kod sözcüğünü yazalım:
6 7
Log-antilog tabloda integer 3 = exp 25 olduğundan,

8

şeklinde olacaktır. Terim sayısına göre üreteç polinomunun değişeceğini gördük ve 10 adet hata düzeltme kod sözcüğü şu şekilde olacaktır:9
Bu aşamadan sonra üreteç polinomunu ile mesaj polinomunu bölüyoruz. Bildiğimiz uzun polinom bölmesi şeklinde olacaktır. Bölünme sırasında üs değeri üreteç polinomun üs değerinden küçük olamaz bu yüzden ilk önce mesaj polinomunu uygun bir terim ile çarpıyoruz kod sözcükleri 10 terimli idi n=10 bu yüzden x^10 ile çarpıyoruz.

10
şeklinde olacaktır. Üreteç polinomun baş terimi mesaj polinomu ile aynı üs değerinde olmalıdır bu yüzden x^15 ile çarpılır.11
Şimdi yinelemeli bölünme adımlarını gerçekleştirmek mümkün. Bölünme adımının sayısı mesaj polinom terimlerin sayısına eşit olmalıdır. Bu durumda, bölünme işlemini tamamlamak için 16 adım uygulayacağız. Evet 16 adım ama hepsini sığdıramayacağımız için korkmayın kısa bir şekilde sonuca ulaşacağız. Bu da 10 terimli bir kalana neden olacaktır. Bu terimler gerekli olan 10 adet hata düzeltme kod sözcükleri olacaktır.

Adım 1a: İlk adım mesaj polinomun baş terimi ile üreteç polinomunu çarpıyoruz. Bu durumda baş terim 32x^25 dir. Alpha gösterimi ile daha kolay çarpma işlemi yapacağımızdan 32’ yi α^5 şeklinde yazalım.

12
α=2 idi hatırlayalım. Bunları log-antilog tablomuzda detaylı olarak görebilirsiniz burada integer değerlerinin üs olarak karşılığı var. Bkz. tablo için tıklayın.
α^5 göre üreteç polinomunu çarpalım.1314
üs kısım eğer 256 veya büyükse mod 255 yapıyoruz.
15
16
integer şekline dönüştürdük.

Adım 1b:
Mesaj polinomunun katsayılarını üreteç polinomunun katsayıları ile XOR kapısından geçirelim. Önce mesaj polinomunun katsayılarını tekrar yazalım: 32, 91, 11, 120, 209, 114, 220, 77, 67, 64, 236, 17, 236, 17, 236, 17171819

Adım 2a: Bir önceki adımdaki XOR kapısından geçirdiğimiz polinomun baş terimini  üreteç polinomu ile çarpıyoruz. 89 log-antilog tablomuza göre exp 210’a eşit. Üreteç polinomunu           α^210 ile çarpıyoruz. 20
21

integer notasyonuna dönüştürelim:

22

Adım 2b: Bir sonraki XOR gerçekleştirmek için adım 1b’nin sonucunu kullanıyoruz. (89,110,114….,236,17)2324
Bir sonraki adımda ise,  adım 2b de polinomun baş terimi 61 olarak geldi ve 61 log-antilog tablomuza göre 228’a eşit.

26

üreteç polinomunu

27

ile çarpıyoruz. Bir sonraki XOR’u gerçekleştirmek için adım 2b’nin sonucunu kullanıyoruz.
Bu şekilde bu sıralamaya göre işlemleri tekrarlayarak devam ediyoruz ve 16. adımda elde ettiğimiz polinom:28

Veri kod sözcüklerini ve hata düzeltme kod sözcüklerini artık oluşturduk. Şimdi ise, final mesajının yapısının nasıl harmanlandığını açıklayacağız. Veri (data) kod sözcüklerine ve bunlara karşılık gelen hata düzeltme kod sözcüklerine ihtiyacımız var. Bir sonraki adımda ise verilen hata düzeltme tablosuna göre veri kod sözcüklerine ve bunlara karşılık gelen hata düzeltme kod sözcüklerini yazıp ikisini birbirine harmanlayacağız. Haydi bakalım.
QR kodlarının hata düzeltmesi marifeti, düzeltilmesi gereken veri miktarıyla doğrudan ilişkilidir. Mesela bir QR Kod içerisinde 50 adet veri kodlanması gerekiyor, ve bu 50 verinin yarısı yani 25 adedinin kurtarılabilir olmasını istersek, Reed-Solomon kod da hata düzeltme için ayrıca 50 veriye daha ihtiyaç duyar. Şöyle ki, Reed-Solomon kodu, düzeltilecek verinin tam iki katı veriye ihtiyaç duymaktadır. Bu da QR kod boyutunu arttıran bir etkendir. Mesela kodunuz hasar gördü üstüne çay döküldü buna rağmen veriyi düzgün okumak için hata düzeltme kod sözcükleri kullanılır. Örnek olarak, bir 5-Q QR kodunu oluşturmak için, aşağıda gösterilen hata düzeltme tablosu bize diyor ki  5-Q kodu 62 veri kod sözcüklerine (8-bit ikili sayıların dizeleri) sahiptir.
Hata düzeltme tablosunda 5-Q kodunun ilk grubu 2 bloktan ve blok başına 15 veri kod sözcüğünden oluşur. İkinci grup ise 2 bloktan oluşur ve blok başına 16 veri kod sözcüğü vardır. Fakat hatırlayacağımız üzere 5-Q kodunun blok başına 18 adet hata düzeltme kod sözcüğü olduğunu unutmayalım.

Sürüm ve Hata düzeltme seviyesi Toplam kod sözcükleri sayısı ve EC seviyesi Blok başına hata düzeltme kodu 1. gruptaki blok sayısı 1. gruptaki blokların her birinin veri kod sözcükleri sayısı 2. gruptaki blok sayısı 2. gruptaki blokların her birinin veri kod sözcükleri sayısı Toplam Kod sözcükleri
5-L 108 26 1 108 (108*1) = 108
5-M 86 24 2 43 (43*2) = 86
5-Q 62 18 2 15 2 16 (15*2) + (16*2) = 62

Hata düzeltme kod sözcükleri tablosu için tıklayınız.

Şimdi tabloya göre veri kod sözcükleri sol baştan tamsayı (integer) halinde: 67,85,70,134,87,38,85,194,119,50,6,18,6,103,38 bu sayılar nasıl hata düzeltme kod sözcüklerine (error correction codewords) dönüştü onu görelim: 213 199 11 45 115 247 241 223 229 248 154 117 154 111 86 161 111 39

Yukarıdaki tabloda 5-Q kodunun blok başına 18 adet hata düzeltme kod sözcüğü olduğunu söylemiştik. Bu örnekte, dört blok var o halde 18 adet hata düzeltme kod sözcükleri dört set olacak ve toplam 72 adet hata düzeltme kod sözcüğü olarak karşımıza çıkacaktır.

İlk adım olarak mesaj polinomunu bölünmesi için hazırlıyoruz: (67,85,70,134,87,38,85,194,119,50,6,18,6,103,38)29
Baş terimin üssü bölme sırasında bölünenden küçük olamayacağı için, mesaj polinomunu hata düzeltme kod sözcükleri sayısı kadar çarparız. Tabloda n=18 olduğu için x^18 ile çarparız ve:
30
Üreteç polinomunu oluştururken önce 18 error correction codewords olarak yazarız :
31
fakat üreteç polinomunun baş terimi aynı zamanda aynı üsse sahip olmalı bu yüzden x^14 ile çarparız:
32
Yukarıdaki HELLO WORLD deki bölme işlemi ile aynı adımları tekrarlayacağız. Bu sefer 15 adımda bölme işlemini tamamlayacağız çünkü mesaj polinomu terim sayımız 15 idi.
15. adımda geldiğimiz sonucu direk olarak yazıyorum: 33

Hata düzeltme kod sözcüklerini orijinal mesaj polinomu için kullanılacak polinom terimleri şunlardır:
213  199  11  45  115  247  241  223  229  248  154  117  154  111  86  161  111  39

Hata düzeltme kod sözcüklerimizi oluşturduğumuza göre bunları bir harmanlayalım karıştıralım:

Veri kod sözcüklerini yazalım önce sütun şeklinde:harman1Sütun şeklinde kod sözcüklerini harmanlıyoruz şöyle ki: 67, 246, 182, 70, 85, 246, 230, 247, 70, 66, 247, 118, 134, 7, 119, 86, 87, 118, 50, 194, 38, 134, 7, 6, 85, 242, 118, 151, 194, 7, 134, 50, 119, 38, 87, 16, 50, 86, 38, 236, 6, 22, 82, 17, 18, 198, 6, 236, 6, 199, 134, 17, 103, 146, 151, 236, 38, 6, 50, 17, 7, 236

Hata düzeltme kod sözcükleri:harman2

Sütun şeklinde hata düzeltme kod sözcüklerini harmanlıyoruz aynı şekilde: 213, 87, 148, 235, 199, 204, 116, 159, 11, 96, 177, 5, 45, 60, 212, 173, 115, 202, 76, 24, 247, 182, 133, 147, 241, 124, 75, 59, 223, 157, 242, 33, 229, 200, 238, 106, 248, 134, 76, 40, 154, 27, 195, 255, 117, 129, 230, 172, 154, 209, 189, 82, 111, 17, 10, 2, 86, 163, 108, 131, 161, 163, 240, 32, 111, 120, 192, 178, 39, 133, 141, 236

ve final mesaj olarak ikisini yanyana koyup binary’e (ikili) çeviriyoruz:

Final mesajımız: 67, 246, 182, 70, 85, 246, 230, 247, 70, 66, 247, 118, 134, 7, 119, 86, 87, 118, 50, 194, 38, 134, 7, 6, 85, 242, 118, 151, 194, 7, 134, 50, 119, 38, 87, 16, 50, 86, 38, 236, 6, 22, 82, 17, 18, 198, 6, 236, 6, 199, 134, 17, 103, 146, 151, 236, 38, 6, 50, 17, 7, 236, 213, 87, 148, 235, 199, 204, 116, 159, 11, 96, 177, 5, 45, 60, 212, 173, 115, 202, 76, 24, 247, 182, 133, 147, 241, 124, 75, 59, 223, 157, 242, 33, 229, 200, 238, 106, 248, 134, 76, 40, 154, 27, 195, 255, 117, 129, 230, 172, 154, 209, 189, 82, 111, 17, 10, 2, 86, 163, 108, 131, 161, 163, 240, 32, 111, 120, 192, 178, 39, 133, 141, 236

67 = 01000011
246 = 11110110
182 = 10110110
70 = 01000110

ve mesajın ilk 32 biti şöyle olacaktır: 01000011111101101011011001000110

Bir sonraki yazımızda bu verilerimizi matris içine yerleştireceğiz. Bakalım neler olacak, şimdilik hoşçakalın ve takipte kalın.

Bahar Uğurdoğan hakkında 8 makale
Kriptolojistimsi.

1 geri izleme / bildirim

  1. SonBAHAR’ın ilk kodlama dersleri | Paul Erdos

Bir yanıt bırakın

E-posta hesabınız yayımlanmayacak.


*