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

Format (Biçim) ve Sürüm Bilgisi

Bildiğimiz gibi QR kodları, hata düzeltme kodları (error correction codes) ve maske desenleri kullanır. QR kodunun büyüklüğü bir sayı ile temsil edilir ve buna sürüm numarası denir demiştik. QR kodu tarayıcılarının kodları düzgün taraması için biçim ve sürüm bilgisine ihtiyaç vardır. QR code tarayıcıları, taranan kodda hataları tespit etmek ve düzeltmek için kullanabileceği tekrarlı verileri üretir. QR kodları aynı zamanda maske desenleri kullanır demiştik.
QR kodları bir biçim dizesi içermesi gerekir yani hangi seviyede hata düzeltme kod (error correction coding) bilgisi ve kod içerisinde hangi maske kullanılmış bunun bilgisi gerekmektedir. Biz size 28 olası biçim dizeleri listeleyeceğiz.
Biçim (format) bilgisi dizesi, geçerli QR kodda kullanımı olan hata düzeltme seviyesi ve maske desenini kodlar. Dört olası hata düzeltme seviyesi (L, M, Q ve H) ve yedi olası maske deseni olduğundan, 28 (4*7) olası biçim bilgisi dizesi vardır. Biçim dizesi her zaman 15 bit uzunluğundadır. Bir dize oluşturmak için, ilk beş bitlik dize oluşturulur, hata düzeltme seviyesi ve maske deseni kodlanır. Daha sonra 10 adet hata düzeltme bitlerini oluşturmak için bu beş bit kullanılır. Elde edilen bu 15 bit maske deseni ile XOR kapısından geçirilir. Bakalım detaylar nasılmış. Bir biçim dizesi oluşturmak için ilk adım QR kodlarından kullanılan hata düzeltme seviyesi belirlenir ve ilk 2 biti alınır. Aşağıdaki tabloda, her hata düzeltme seviyesi için bit değerlerini göstermektedir.
ecl

Maske desenlerini hatırlayalım:
maskedesen

Örneğin hata düzeltme seviyesi L ve maske desen göstergesi 100 olanı kullanalım. İlk beş biti yazalım:

01 (hata düzeltme seviyesi L göstergesi)
100 (maske desen göstergesi tabloya bakın)

Sonuç: 01100 Şimdi biçim dizemiz için ilk 5 bitimiz var fakat 10 bit yapmamız için hata düzeltme bitleri üreteceğiz. Bu adım da yine Reed-Solomon hata düzeltme kullanacağız fakat bir öncekiler gibi uzun olmayacak çünkü polinomlar 15 terimden fazlasını içermez ve katsayıların hepsi 1’ler ve 0’lardan oluşur. Biçim dizesinin hata düzeltme kod sözcüklerini oluştururken, QR kodu spesifikasyonu üreteç polinomu olarak şunu kullanır:
polinom1
Her terimin katsayılarını alarak binary formuna çevirebiliriz. Örneğin x^10 katsayısı 1, x^9 katsayısı 0 dır. Noluyo bu nasıl oldu diyenler için panik yok. Polinoma bakıyoruz var olanlar için 1 yok olanlar için 0 diyoruz. Bu şekilde binary dizemizi oluşturuyoruz.

10100110111

Hata düzeltme (Error Correction) bitlerinin hesaplanması
Bir sonraki adımda üreteç polinomunu (10100110111) biçim (format) dize bitlerine (01100) bölüyoruz. Bunu yapmak için öncelikle biçim dize bitini (01100) 15 bite dönüştürmemiz lazım. Sağ tarafına 10 tane 0 koyarak ekliyoruz: 01100 -> 011000000000000 daha sonra sol taraftan sıfırları kaldıralım ve bölme işlemini gerçekleştirebiliriz:
011000000000000 -> 11000000000000

10 veya daha az bit uzunluğunu elde edene kadar polinomu bölmek zorundayız. Bu nedenle, her bölümün adımından önce, geçerli biçim dizesinin 11 bit ya da daha uzun olduğunu kontrol edin. (11 bit üreteç polinomu uzunluğu) Bizim mevcut dizemiz 11000000000000, 14 bit uzunluğundadır.

Adımları şu şekilde izliyoruz:

  1. Üreteç polinomuna gerekli ise biçim dizesi boyutunu elde edene kadar sağdan 0 eklenir.
  2. Biçim dizesi ile üreteç polinomu XOR’lanır. ^
  3. Elde edilen ikilinin sol başındaki sıfırlar yok edilir.

Birinci Bölme:
10100110111 <– üreteç polinomumuz eklentisiz
11000000000000 <– biçim dizemiz
10100110111000 <– üreteç polinomunu sağdan 0’lar ile biçim dizesi boyutuna getirdik.

Şimdi ise biçim dizesini üreteç polinomumuz ile XOR’layacağız :
11000000000000 ^ 10100110111000 = 01100110111000
elde ettiğimiz ikilinin yine soldan 0’larını yok ediyoruz.
01100110111000 ->  1100110111000

İkinci Bölme
Elde edilen dize 1100110111000 13 bit uzunluğunda. 11 bit veya daha uzun olduğu için bölmeye devam edebiliriz. Aynı işlemleri tekrarlıyoruz.

10100110111 <– üreteç polinomumuz eklentisiz
1100110111000 <– Biçim dizemiz
1010011011100 <– eklentili üreteç polinomumuz

biçim dizesini eklentili üreteç polinomumuz ile XOR’layacağız :
1100110111000 ^ 1010011011100 = 110101100100

Üçüncü Bölme
Elde edilen dize 110101100100 12 bit uzunluğunda. 11 bit veya daha uzun olduğu için bölmeye devam edebiliriz. Aynı işlemleri tekrarlıyoruz.

10100110111 <– üreteç polinomumuz eklentisiz
1100110111000 <– Biçim dizemiz
101001101110 <– eklentili üreteç polinomumuz

biçim dizesini eklentili üreteç polinomumuz ile XOR’layacağız :
110101100100 ^ 101001101110 = 011100001010
Soldan sıfırları silmeyi unutmuyoruz. 011100001010 -> 11100001010

Dördüncü Bölme
Elde edilen dize 11100001010 11 bit uzunluğunda. 11 bit veya daha uzun olduğu için bölmeye devam edebiliriz. Aynı işlemleri tekrarlıyoruz.
Biçim dizesi ile aynı uzunlukta olduğundan üreteç polinomuna eklenti yapmamıza gerek kalmadı.
Biçim dizesini eklentili üreteç polinomumuz ile XOR’layacağız :
11100001010 ^ 10100110111 = 1000111101
Elde edilen dizemiz 10 bit uzunluğunda. Böylece bölme işlemini tekrarlamamıza gerek kalmadı. Eğer sonuç 10 bit den daha kısa olsaydı, 10 bit elde etmek için dizenin sol tarafına 0’lar ekleyecektik.

Şimdi format ve hata düzeltme bitlerini birlikte düzenleyelim.
Beş-bit format dizemiz: 01100
Bölünme aşamasında 10-bit hata düzeltme dizemiz: 1000111101
Birleştirilmiş dize: 011001000111101

Maske dizesini XOR’layalım
OR kodları spesifikasyonu gereği şu ikili dize ile bulduğumuz sonucu XOR yapmamızı söylüyor: 101010000010010

011001000111101 ^ 101010000010010 = 110011000101111
Şimdi hata düzeltme seviyesi L, maske desen göstergemiz 100 ve biçim dizemiz 110011000101111

QR kodu içine nasıl biçim dizesi yerleştirilir?
Aşağıdaki resimde gösterildiği gibi biçim bilgisi dizemiz, en üstteki bulucu desen (finder pattern) altında ve en soldaki bulucu desen sağında yer alıyor. Qr kodunda temsil edilen sayılar bizim biçim dizemizi şu şekilde temsil ediliyor.
formatdize
format

Bu arada şu karanlık noktayı açıklayalım, her QR kodun karanlık bir modül olarak bilinen karanlık bir pikseli olması gerekir. Koordinatları ise şöyle bulunur: (8, 4 * versiyon + 9). Bizde versiyon 1 olduğu için 4 ile çarpıp 9 eklediğimizde y koordinatını buluruz. (8,13) Diğerleri için :

sürüm (versiyon) 1: 4*1 + 9 = 13
sürüm (versiyon) 2: 4*2 + 9 = 17
sürüm (versiyon) 3: 4*3 + 9 = 21

Qr kodumuz içine biçim dizemizi yerleştirelim ve bu bölümü bitirelim. formatson
Sürüm bilgisinden bahsetmedin diyenler için hemen kısaca bahsedelim. Eğer QR kodunuz versiyon 7 ve üzerindeyse QR kodunun sol alt ve sağ üst köşelerinde 18-bitlik dizeler halinde sürüm bilgileri yerleştirilir.  Sürüm bilgisi aynen yukarıdaki adımlar gibi yapılır fakat burada Golay kodlar (18,6) kullanılır. Bu nedenle sürüm bilgileri dizesi 18 bitlik bir dizedir. Bunun 12 biti error correction bitleri diğer 6 sıda sürüm bilgisi dizesidir. Tüm dize 18 bit demiştik. Her seviyede 28 olası biçim dizelerinin listesini bu tablodan bulabilirsiniz. Tıklayın.

Bir sonraki yazımızı sakın kaçırmayın çünkü en civcivli kısmı en sona bıraktık, QR kodlarına bakarak mesajları deşifreleme (DECODING) işlemi için takipte kalın.

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

İlk yorum yapan olun

Bir yanıt bırakın

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


*