SonBAHAR’ın ilk kodlama dersleri – Paul Erdos // Akademik Matematik Blogu
19 Eylül 2016 Bahar Uğurdoğan Matematiğin uygulama alanları 0
QR Kodları Bölüm 1
Merhaba arkadaşlar, bu yazımızda yap-boz yapmaktan sıkılanlar için güzel bir çalışma hazırladım. Uğraşayım ama farklı birşey olsun, birazda dijital olsun diyenler için kendi QR kodunuzu matematik kullanarak ve birazda kodlama teorisi (coding theory) sosuna az ucundan banarak can sıkıntınızı giderebileceksiniz. Ayrıca bu yazının esas hedefi var olan yani taranmış (scan) edilmiş QR kodlarının EL ile deşifre (decode) edilmesidir. Cep telefonunuz arızalandı diyelim, üzerine çay döküldü vs. acil bir kodu okutmak zorundasınız. Bu yazımızdan yararlanarak bunu yapabilirsiniz, hem eğlenmek hem de öğrenmek isteyen meraklı beyinler için perde aralanıyor:
Tanım ve çalışma şekli
QR kodu; sayıları, harfleri ve Kanji karakterleri (Japon karakterler) gibi bilgileri kodlamak için özel iki boyutlu barkod türüdür. Neden Japon karakterlerini şifrelemek (encode) isteyelim ki diyen arkadaşlara söylüyorum, 1994 yılında Japon Denso firması bunu geliştirmiştir. Aslında otomotiv alanında kullanılması planlanıyordu. Japonya’dan sonra Güney Kore’de de oldukça yaygınlaşmıştır. Dijital kameralı son model mobil cihazlarınızda QR kodu okuyucu ile birlikte bilgiye hızlı ve anında ulaşabiliyorsunuz. Aslında açılımı Quick Response yani hızlı, çabuk tepki demektir. Kodlama işlemi (encoding process) karmaşık bir işlemdir özellikle hata düzeltme kodu (error correcting code) kelimelerini oluşturma aşaması sırasında tam bir kabusa dönüşebilir. Fakat biz bunu kolaylaştıracağız. Bu yazımızda QR kodunun yapısını öğrenmek isteyen programcı olan ya da olmayan arkadaşlar için biraz bahsedeceğiz. Bazı temel programlama bilgisine sahip olduğunuzu varsayarak başlayalım.
En küçük QR kodları 21×21 piksel ve en büyüğü ise 177×177 pikseldir. Bu boyutlara versiyon (sürüm) denilmektedir. Örneğin 21×21 piksel versiyon 1, 25 x 25 piksel versiyon 2 ve bu şekilde devam eder. 177 x 177 piksel ise versiyon 40’dır.
Bir QR kodunun kapasitesi sürümüne ve hata düzeltme seviyesine bağlıdır. Bunun yanı sıra kodlayan verilerin tipi de önemlidir. QR kodunu kodlayabilmek için 4 veri modu kullanır: Sayısal, Alfanümerik, Byte (ikili) ve Kanji (Japon karakterler).
Genel Bakış: QR Kod oluşturma
1) Veri (data) Analizi
Bir QR kod metin dizesini kodlar. Bu metni kodlamanın dört modu vardır demiştik: Sayısal, alfanümerik, byte (ikili) ve Kanji. Her mod bit (1’ler ve 0’lar) bir dizge olarak metni kodlar, ancak her mod bitleri metine dönüştürmek için farklı bir yöntem kullanır ve her kodlama yöntemi bitlerin mümkün olan en kısa dizeyle veriyi kodlamak için optimize edilmiştir. Bu nedenle ilk adımda seçeceğimiz metin için en uygun modu seçmemiz gerekmektedir. Yani sayısal, alfanümerik, byte (ikili) veya Kanji modunda kodlanmış olup olmadığını belirlemek için veri (data) analizi yapmamız şarttır. Bahsettiğimiz dört adet kodlama modu aşağıdaki karakterleri içerir:
Sayısal mod ondalık basamak 0’dan 9’a kadar içindir.
Alfanümerik mod, ondalık 0 ile 9 arasındaki basamak yanı sıra büyük harflerle (Küçük harfe değil), ve semboller $,% içindir *, +, -, /, ve SPACE (boşluk) için kullanılır.
Byte modu, varsayılan olarak, ISO-8859-1 karakter kümesinden karakterler içindir. Ancak, bazı QR kod tarayıcılar UTF-8 yerine byte modunda kullanıldığında otomatik olarak algılayabilir.
Kanji modu, Shift JIS karakter kümesinden çift baytlık karakterler içindir. UTF-8 Kanji karakterleri kodlamak mümkün olmakla birlikte, bunu yapmak için üç ya da dört bayt kullanmanız gerekir. Öte yandan, JIS Shift, her Kanji karakteri kodlamak için sadece iki bayt kullanır, böylece Kanji modu Kanji karakterlerini daha verimli sıkıştırır.
2) Veri Kodlama
Şimdi metin için uygun kodlama modunu seçmiş olduğumuza göre, bir sonraki adım metni kodlamak olacaktır. Fakat verilerin kodlanmasından önce, hata düzeltme düzeyini seçmemiz gerekir. QR kodları dört hata düzeltme seviyeleri ile Reed-Solomon hata düzeltme algoritması kullanır. Reed-Solomon kodu aslında müzik CD’leri vb. için kullanılan matematiksel bir hata düzeltme yöntemidir. Bu yöntem, kodlanmış verilere dayalı olarak hata düzeltme kod sözcüklerini (error correcting codewords) oluşturur. Kod sözcükleri 8 bit uzunluğundadır ve eğer veri doğru olarak okunmadıysa, QR kod okuyucu hata düzeltme bitlerini belirlemek için kullanılabilir ve hata düzeltme kod sözcükleri bu hataları düzeltmek için kullanılabilir.
Hata düzeltmenin dört düzeyi vardır: L, M, Q, H.
Hata Düzeltme Düzeyi Hata Düzeltme Özelliği
L (Low – Düşük) verilerin % 7 kurtarır.
M (Medium – Orta) verilerin % 15 kurtarır.
Q (Quartile – Çeyrek) verilerin % 25 kurtarır.
H (High – Yüksek) verilerin % 30 kurtarır.
Dikkat edilirse hata düzeltme yüksek seviyelerde daha fazla bayt gerektirir, böylece hata düzeltme seviyesi ne kadar yüksekse daha büyük QR kodu gerekecektir. Her versiyon (sürüm) kullanım moduna bağlı olarak, maksimum kapasiteye sahiptir. Buna ek olarak, hata düzeltme seviyesinin daha da kapasitesini kısıtlamaktadır. Karakter kapasite tablosu, belirli bir kodlama modu ve hata düzeltme seviyesi için tüm QR sürümleri kapasitelerini listeler. Aşağıda versiyon 1, 2 ve 40 olan versiyonların kapasitelerini listeledik. Tablonun bütün versiyonları çok uzun ve yer kapladığı için şimdilik bu 3 sürümü listeledik.
Versiyon Hata Düzeltme Seviyesi Nümerik Mod Alfanümerik Mod Byte Mod Kanji Mod
1 L 41 25 17 10
2 L 77 47 32 20
40 L 7089 4296 2953 1817
Bu noktada, kodlanacak karakter sayısını saymamız gerekir ve kodlama modu için seçeceğiniz versiyon seviyesindeki en küçük karakteri listeden belirleyip istenen hata düzeltme seviyesini ve en küçük sürümünü belirlememiz gerekir.
Örneğin BAHAR sözcüğünde 5 karakter vardır ve tabloya göre versiyon 1 kullanılarak alfanümerik modda her seviye de kodlama yapılabilir. Fakat HELLO WORLD ifadesinde 11 karakter vardır ve versiyon 1 de, H seviyesinde hata düzeltme, yalnızca alfanümerik modunda 10 karakter içerebilir. Bu sebeple bu ifade için (HELLO WORLD) H seviyesinde versiyon 1 kullanılamaz. Versiyon 1 için diğer seviyelerde kullanılabilir. Karakter içeriğinize göre seçim yapabiliriz. En yüksek kapasiteli QR kodu 40-L (sürüm 40, hata düzeltme seviyesi L) ‘dir. 40-L QR kodu kapasitesini listeleyen bir tablo aşağıda verilmiştir. 40-M, 40-Q ve 40-H ise düşük bir kapasiteye sahiptir çünkü daha fazla hata düzeltme kod sözcükleri için daha fazla alan gerekir.
Kodlama Modu 40-L kodu için maksimum karakter sayısı
Nümerik 7089 karakter
Alfanümerik 4296 karakter
Byte 2953 karakter
Kanji 1817 karakter
Mod Göstergesi (ENCODING)
Kodlanmış veriler kendinden sonra gelen bit için kullanılan modu belirtir bu yüzden uygun mod göstergesi ile başlamalıdır. Tabloda, her mod için mod göstergelerini listeledik. Örneğin alfanümerik modda HELLO WORLD için mod göstergesi 0010’dur.
Mod Adı Mod Göstergesi
Nümerik Mod 0001
Alfanümerik Mod 0010
Byte Mod 0100
Kanji Mod 1000
Karakter Sayısı Göstergesi (Karakter sayısı bit uzunluğu)
Karakter sayısı göstergesi kodlanmış olan karakter sayısını temsil eden bitin bir dizesidir. Karakter Sayısı Göstergesi, mod göstergesi belirlendikten sonra eklenmelidir. Ayrıca, karakter sayısı göstergesi QR sürümüne bağlı olarak, uzun bit içeren belirli bir sayı olmak zorundadır. Daha sonra orijinal metnin karakter sayısını sayarak, metni ikili sayı sistemine dönüştüreceğiz. Karakter sayısı göstergesinin uzunluğu kodlama moduna bağlıdır ve QR kod versiyonu da kullanımda olacaktır. Örneğin QR kodunu, HELLO WORLD ifadesini alfanümerik modda versiyon 1 ile kodlarsak, karakter sayısı göstergesi de 9 bit uzunluğunda olmalıdır.
Versiyon 1 ile 9 arası Versiyon 10 ile 26 arası Versiyon 27 ile 40 arası
Nümerik mod: 10 bit Nümerik mod: 12 bit Nümerik mod: 14 bit
Alfanümerik mod: 9 bit Alfanümerik mod: 11 bit Alfanümerik mod: 13 bit
Byte mod: 8 bit Byte mod: 16 bit Byte mod: 16 bit
Kanji mod: 8 bit Kanji mod: 10 bit Kanji mod: 12 bit
HELLO WORLD karakter sayısı 11’dir. İkili sistemde 11’in karşılığı 1011 dir. 9 bit uzunluğuna getirmemiz için öncelikle sol kısmı dolduralım: 000001011.
Alfanümerik Mod Kodlama
HELLO WORLD ifadesini kodlayacağız fakat dikkat etmemiz gereken en önemli şey alfanümerik modu yalnızca büyük harf içerir bunu unutmayalım.
İlk olarak karakterleri çiftler halinde ayıralım: HE, LL, O , WO, RL, D
Alfasayısal modunda her bir alfa sayısal karakter bir sayı ile temsil edilmektedir. Bu sayıları bulmak için alfanümerik tablo için tıklayınız. Soldaki sütun alfanümerik karakterleri gösterir ve sağdaki sütun onun temsil ettiği sayısını gösterir. Her karakter çifti için, ilk karakteri (alfanümerik tablodan) temsil eden sayıyı alın ve 45 ile çarpın. Çünkü tabloda 45 adet harf ve sayı karşılığı var. Çıkan sonucu ikinci karakterin sayısını temsil eden bu sayıya ekleyin. Örnek:
HELLO WORLD ifadesinin ilk çifti HE.
H → 17 E → 14
(45 * 17) + 14 = 779 Şimdi ,11-bit ikilik sisteme bu numarayı dönüştürelim, eğer 11 bit olmazsa 0’larla soldan doldurma işlemi yapabilirsiniz.
779 → 01100001011
Eğer karakteri tek sayıda kodluyorsanız aynen burada olduğu gibi, son karakterin sayısal gösterimini alabilir ve 6-bit ikili dizeye dönüştürebilirsiniz.
Mod Göstergesi Karakter Sayısı Göstergesi Kodlanmış Veri (Encoded Data)
Kodlanmış veri dizisi elde edildikten sonra, QR kodunun toplam kapasitesini doldurmak için 0’lar ve bayt ile doldurmamız gerekebilir. Bir QR kodunda kaç adet veri biti gerekli olduğunu belirlemek için, aşağıda verilen hata düzeltme tablosundan yararlanırız. Versiyon ve hata düzeltme seviyesi için gerekli olan veri bitlerinin toplam sayısını elde etmek için 8 ile çarpılır. Örneğin, tabloya göre, sürüm 1-Q kodu için toplam 13 veri kod sözcüğü vardır. Bu nedenle, bu QR kodu için gerekli bit sayısı 13 * 8 yani 104 bittir. Gerekli ise sonlayıcı (terminator) 0’lar ekleyebiliriz de. Eğer bir bit dizisi gerekli olan bit sayısından 4 bit daha fazla kısaysa, sonuna 4 adet sıfır eklenir.
Aşağıdaki tabloda QR kodu sürümü ve hata düzeltme (EC) seviyesi üretmek için gerekli olan hata düzeltme kodu kelimelerin sayısını listeler. Bu değerler, belirli bir Reed-Solomon bloğu için kaç adet veri baytı gereklidir sorusunu yanıtlar ve ayrıca hata düzeltme baytını da belirlemek için kullanılabilir.
Sürüm ve hata düzeltme seviyesi Sürüm ve hata düzeltme seviyesi veri kod kelimeleri sayısı EC Blok Başına Kod kelimeleri 1.Gruptaki Blok sayısı Veri kod sözcükleri toplamı
1-L 19 7 1 (19*1) = 19
1-M 16 10 1 (16*1) = 16
1-Q 13 13 1 (13*1) = 13
Örneğin, sürümü 1-Q olan HELLO WORLD kodlamasının gerekli bit sayısı 104 bittir. Bizim veri bit dizimiz yukarıda görüldüğü üzere toplam 74 bittir. Terminator (sonlandırıcı) sadece en fazla 4 bit uzunluğunda olabilir, bu yüzden dize sağına dört sıfır eklememiz gerekir. Sonuçta elde edilen dize hala 104 bit kapasitesini doldurmak için çok kısa ama QR kodunun spesifikasyonu gereği en fazla dört adet sıfır olmalıdır. Eğer 104 bit yerine veri bit dizimiz 102 bit olsaydı, sonlandırıcının uzunluğu sadece 2 bit olacaktı.
Mod Göstergesi Karakter Sayısı Göstergesi Kodlanmış Veri (Encoded Data) Terminator (Sonlandırıcı)
Sonlandırıcı ilave edildikten sonra, dizede bit sayısı 8 bir katı değilse, dize uzunluğunu 8’in bir katı yapmak için sağdan sıfır eklenir.
HELLO WORLD dizeye sonlandırıcı ekledikten sonra, uzunluk 78 bit uzunluğunda oldu. Bu bit dizisini 8-bit ikili olarak yazalım fakat bu dize 8’in bir katı değil:
00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 010000
dikkat edildiyse sonunda 6 bit var ve 8-bit ikili yapmak için iki tane 0 ekleyelim:
Dize hala maksimum kapasite doldurmak için yeterince uzun değilse dize maksimum uzunluğu ulaşıncaya kadar tekrar ederek, dizenin sonuna aşağıdaki baytları ekleriz:
11101100 00010001 Bu baytlar, sırasıyla 236 ve 17 ile eşdeğerdir. Bit dizisi çok kısa ise bu sayılar istenilen bit uzunluğuna erişinceye kadar eklenir.
Şu an HELLO WORLD dizemiz 80 bit uzunluğundadır. 00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 01000000. 1-Q kodu için gerekli kapasite 104 bittir. Bizim 104 bit uzunluğuna ihtiyacımız var yani 24 bit daha eklememiz gerekmektedir. 24/8 = 3 Böylece 3 bayt veri dizenin sonuna eklenmelidir.
Şimdi ham veri bitleri elde ettik, Alfanümerik mod kodlamayı kullanarak HELLO WORLD örneğini kullanacağız. Hata düzeltme kodlarını (error correcting codes) oluştururken bu kod sözcükleri mesaj polinomun katsayıları olarak kullanılacaktır.
Bunu nasıl deşifre (decode) edeceğiz acaba diyenler için ufak bir not:
Maskeleme desenini öğrendikten sonra, desenin kuralına göre bitleri tersine çevirin. Daha sonra benim yukarıda yaptığım gibi 0 ve 1 leri ekleyin. Yukarıdan aşağıya zikzak gidiyorsunuz. Bunları deşifreleme (decoding) kısmında ayrıntılı bir biçimde anlattım, daha sonra da bitleri yazın örnek ilk 11’li çiftimiz mavi kısımda : 01100001011 = 779 değerine karşılık geliyor.
779 : 45 (bölüm 17 ilk harf) 779-765 (45*17)=14 ikinci harf
17: H 14: E
Şimdi ise hata düzeltme kodları (error correction codes) nasıl oluşturulur onu göreceğiz. SonBAHAR bitmeden kodlamayı öğreneceğiz, bir sonraki yazımız için tıklayın >>>
Asallardan nükleer fiziğe ve ötesine
Olasılık ya da Yapay Zekanın Matematiksel Temelleri – 3