QR kodu adım adım nasıl oluşturulur

 (nayuki.io)
5 puan yazan GN⁺ 2024-11-19 | 1 yorum | WhatsApp'ta paylaş
  • Metnin QR koda dönüşmesinin iç süreci 0~9. adımların görselleştirmesiyle izlenebiliyor; Nayuki QR Code generator library’nin çalışma mantığı görülebiliyor
  • Örnek girdi Hello, world! 123, 17 Unicode code point olarak analiz ediliyor ve Numeric·Alphanumeric·Kanji değil, Byte modu ile kodlanıyor
  • Mod bitleri, karakter sayısı, segment verisi ve sonlandırma bitleri art arda eklenince 19 veri codeword’ü oluşuyor ve Version 1’in ECC L kapasitesine sığıyor
  • Version 1 QR kodu, 1 blok içinde 19 veri codeword’üne Reed–Solomon ECC codeword’ü 7 adet ekledikten sonra sabit desenleri ve veri modüllerini yerleştiriyor
  • 8 maskenin penalty değerleri karşılaştırılarak toplam puanı en düşük olan Mask pattern 3 seçiliyor; nihai sonucun yalnızca basit bir kodlama değil, kalite değerlendirmesinden de geçerek belirlendiği görülüyor

Demonun amacı ve girdinin işlenmesi

  • Bu web uygulaması, bir metin dizgesinin QR kod olarak nasıl kodlandığını adım adım görselleştirir
  • Sayfa, QR Code generator library’nin iç işleyişini anlamayı kolaylaştırmak için kodlama sürecini ayrıntılandırır
  • Kullanıcı girdisi alanları metin dizgesi, hata düzeltme seviyesi, minimum Version zorlaması ve maske deseni zorlamasından oluşur

0. adım: Unicode karakter analizi

  • Örnek dizge Hello, world! 123 olup, giriş metnindeki code point sayısı 17’dir
  • Her karakterin Numeric, Alphanumeric, Byte, Kanji modlarında kodlanıp kodlanamayacağı kontrol edilir
  • Tüm dizgenin modlara göre kodlanabilirliği şöyledir
    • Numeric: mümkün değil
    • Alphanumeric: mümkün değil
    • Byte: mümkün
    • Kanji: mümkün değil
  • Tüm karakterleri kapsamak için seçilen segment modu Byte’tır

1. adım: Veri segmenti oluşturma

  • Her karakter bir bit dizisine dönüştürülür
  • Numeric ve Alphanumeric modlarında ardışık karakterler gruplanarak kodlanır
  • Byte modunda tek bir karakter 8, 16, 24, 32 bit seçeneklerinden birini üretir
  • Örnekte her karakterin onaltılık değeri 8 bite dönüştürülür
    • H: 48 → 01001000
    • e: 65 → 01100101
    • 1: 31 → 00110001
    • 2: 32 → 00110010
    • 3: 33 → 00110011
  • Demo programı, basitleştirme amacıyla her zaman tek segment oluşturur
  • Toplam bit uzunluğunu azaltan en iyi bölümlendirme yöntemi ayrıca optimal text segmentation for QR codes içinde ele alınır

2. adım: Version numarasını uyarlama

  • Segment listesini ifade etmek için gereken toplam bit uzunluğu Version aralığına göre değişir
    • Version 1~9: 148 bit, 19 codeword
    • Version 10~26: 156 bit, 20 codeword
    • Version 27~40: 156 bit, 20 codeword
  • Codeword 8 bit, yani 1 bayt olarak tanımlanır
  • QR kodun veri codeword kapasitesi, Version’a ve hata düzeltme seviyesine göre değişir
  • Örnek girdi, seçilen hata düzeltme seviyesinde Version 1’e sığar
  • Nihai olarak seçilen Version numarası 1’dir

3. adım: Segmentleri birleştirme, padding ve codeword oluşturma

  • Birden fazla bit dizisi art arda eklenerek veri bit dizisi oluşturulur
    • Segment 0 mode: 0100, 4 bit
    • Segment 0 count: 00010001, 8 bit
    • Segment 0 data: 136 bit
    • Terminator: 0000, 4 bit
  • Birikmiş bit sayısı 152 bit’tir
  • Örnekte Bit padding ve Byte padding ikisi de 0 bittir
  • Toplam veri codeword baytları 8 bitlik birimlere ayrılarak onaltılık biçimde gösterilir
    • 41 14 86 56 C6 C6 F2 C2 07 76 F7 26 C6 42 12 03 13 23 30

4. adım: Bloklara ayırma, ECC ekleme, interleave

  • Örnekteki blok istatistikleri şöyledir
    • Veri codeword sayısı: 19
    • Blok sayısı: 1
    • Kısa blok başına veri codeword’ü: 19
    • Uzun blok başına veri codeword’ü: yok
    • Blok başına ECC codeword’ü: 7
    • Kısa blok sayısı: 1
    • Uzun blok sayısı: 0
  • Veri codeword dizisi kısa ve uzun bloklara ayrılır; her bloğun sonuna ECC codeword’leri hesaplanıp eklenir
  • Reed–Solomon hata düzeltme kodu hesaplamasının matematiksel süreci uzun, sıkıcı ve ilgi çekici olmadığı gerekçesiyle atlanır
  • Nihai codeword dizisi, veri ve ECC codeword’lerinin interleave edilmesiyle oluşturulur
    • 41 14 86 56 C6 C6 F2 C2 07 76 F7 26 C6 42 12 03 13 23 30 85 A9 5E 07 0A 36 C9
  • Zigzag taramada çizilecek nihai bit dizisi de bu codeword dizisinden üretilir

5~6. adımlar: Sabit desenler ve codeword yerleşimi

  • Sabit desen adımında satır 6 ve sütun 6’ya timing pattern çizilir
  • Üç köşeye, separator dahil olmak üzere her biri 8×8 finder pattern yerleştirilir
  • Finder çevresine geçici dummy format bits eklenir
  • Codeword yerleşimi adımında sağ alt köşeden başlayan zigzag tarama hesaplanır
  • Zigzag tarama, işlev modüllerini (function module) atlar ve henüz doldurulmamış modülleri ziyaret eder
  • Veri, ECC ve remainder modülleri, nihai codeword bit değerlerine ve zigzag sırasına göre çizilir
  • Örnek olarak onaltılık codeword C5, ikilik 11000101 değerindedir ve [dark, dark, light, light, light, dark, light, dark] modül dizisini üretir

7~9. adımlar: Maske uygulama ve penalty hesaplama

  • Her maske deseni yalnızca işlev dışı modülleri (non-function module) etkiler
  • Maske; veri, ECC ve remainder modüllerine XOR ile uygulanır
  • Gerçek format bits, finder çevresine çizilir
  • Penalty araması şu unsurları kontrol eder
    • Aynı renkli 5 veya daha fazla modülün art arda geldiği yatay run
    • Aynı renkli 5 veya daha fazla modülün art arda geldiği dikey run
    • Aynı renkli 2×2 box
    • Yatay finder-like pattern
    • Dikey finder-like pattern
    • Koyu ve açık modüllerin dengesi
  • Örnek QR kodun boyutu ve renk oranı şöyledir
    • Kenar uzunluğu: 21
    • Toplam modül: 441
    • Açık modül: 221
    • Koyu modül: 220
    • Koyu modül oranı: 49.887%
    • Yarısına göre sapma: −0.113%
  • 8 maskenin toplam penalty değerleri şöyledir
    • Mask 0: 1204
    • Mask 1: 1134
    • Mask 2: 1084
    • Mask 3: 1081
    • Mask 4: 1121
    • Mask 5: 1100
    • Mask 6: 1189
    • Mask 7: 1137
  • En düşük toplam penalty değerini alan maske Mask pattern 3’tür

Kaynak kod

İlgili okumalar

1 yorum

 
GN⁺ 2024-11-19
Hacker News yorumları
  • QR kod açıklamalarının internette neresine bakarsam bakayım Reed-Solomon hata düzeltme hesaplamasını atlıyor gibi olması üzücü.
    Burada da yazar bunun “uzun, sıkıcı ve pek ilginç olmadığını” söylemiş; ama herkes böyle düşündüğü için artık bulması epey zorlaştı.
    • Lisansüstünde kodlama teorisi dersi almıştım; aldığım dersler arasında en titiz olanıydı ve beşimizin de zorlandığı bir dersti, ama aldığıma değdiğini düşünüyorum.
      Reed-Solomon dönemin ortasını biraz geçtikten sonra ele alındı; özü polinomlara dayanması. Yeterli sayıda nokta varsa polinom tam olarak belirlenir; bu yüzden fazladan noktalar eklerseniz bazıları kaybolsa bile geri yükleyebilirsiniz.
      Geri kalanı bunu ikili veriye uygulama yöntemi, yani sonlu cisimleri kullanma kısmı; matematiksel olarak güzel ama epey karmaşıklaşıyor.
    • Hata düzeltme hesaplamasını şu iki öğretici açıklıyor:
      https://www.thonky.com/qr-code-tutorial/error-correction-cod...
      https://dev.to/maxart2501/let-s-develop-a-qr-code-generator-...
    • https://www.quaxio.com/an_artisanal_qr_code.html ve PagedOut! Issue #2’de, uzun bölme ile hata düzeltme hesaplaması da dahil olmak üzere sıfırdan QR kod oluşturma anlatılıyor.
    • Uzun ve sıkıcı ama aslında bütünün en ilginç kısmı.
    • İlgili bir Wikipedia maddesi var.
  • Yakın tarihli Veritasium videosu I used to hate QR codes. But they're actually genius da bu konuyu ele alıyor.
    https://www.youtube.com/watch?v=w5ebcowAJD8
  • Yazarın aldığı geri bildirimler derlemesi oldukça eğlenceli: https://www.nayuki.io/page/poor-feedback-from-readers
    • İngilizcesi zayıf insanlarla alay etmek ve e-posta gönderenler o ülkenin temsilî bir örneğiymiş gibi bütün bir ülkeyi aşağılayan yorumlar yapmak, gönderenlerden çok blog sahibinin hakkında daha fazla şey gösteriyor.
      Yorumlarda güçlü bir elitist hava hissediliyor. Bloga kabaca göz attığımda Bitcoin bağışı istediğini ve 3 dolar önerdiğini gördüm; bunun önemli bir kısmının işlem ücretleriyle kaybolabileceğini hesaba katmamış gibi.
    • Hoşunuza gitmeyen mesajlar almış olsanız bile, şikâyet ederken hafif ırkçılığı ve yazarın İngilizce becerisine yönelik eleştiriyi işin içine katmamak daha iyi.
    • Kötü İngilizceyle dalga geçmek her zaman aptallık işaretidir. Akıllı insanlar da aptal gibi davranabilir.
    • Kusura bakmayın ama blog yazarı oldukça nahoş biri gibi görünüyor.
      “Hayır, üniversite projen olan chatbot’ta GitHub depomdaki kodu kullanamazsın. Senin kodlama standartların benim standartlarımı karşılamıyor. Ayrıca İngilizcen de berbat” gibi bir hava var.
    • Kişisel blog işletmenin ne kadar zor olabileceğini anlayabiliyorum. Her türlü insanla uğraşmak gerekiyor.
      Neyse ki iyi geri bildirimleri de ayrıca paylaşıyor: https://www.nayuki.io/page/decent-feedback-from-readers
  • Gayet iyi. Aynı tarzda bir decoder da görmek isterdim.
    • Bilgisayar olmadan QR kod okumayı anlatan Piko ve blinry’nin rehberi de hoşunuza gidebilir: https://qr.blinry.org/
    • Katılıyorum. Telefonların karanlık, bulanık ve yaklaşık dörtte biri ekranın dışında kalan QR kodları bile bu kadar hızlı çözmesine her zaman şaşırıyorum.
    • Sıfırdan bir QR reader uygulamayı anlatan bir rehber aramaya devam ediyorum.
      Google’da görünen “şu computer vision kütüphanesini takın, görüntüyü verin, sonuç çıksın” tarzı şeyleri istemiyorum.
      Zaten decode edilmemiş ham görüntü verisinin elimizde olduğunu varsayıp, gerekli tüm algoritmaları adım adım uygulayan bir rehber arıyorum.
  • Açıklama olması güzel. Şahsen ben sadece hızlıca oluşturmak istiyordum; arama yapınca reklam dolu siteler ya da “kullanmak için üye olmalısınız” siteleri çıkıyordu.
    GitHub’da da birkaç tane buldum ama başka sorunları vardı; daha önce kullandığım, iyi tasarlanmış bir kütüphaneyle hızlıca kendim yaptım ve yaklaşık 15 dakika sürdü.
    https://greggman.github.io/qr-code/
    Daha fazla seçenek eklenebilir ama açıkçası çoğu kullanıcının bu seçeneklere ihtiyaç duyacağını sanmıyorum.
    • İşine yaradığına sevindim. Ben de bir süredir uygulamasını kendim denemek istiyordum; bulabildiklerim yalnızca Python veya Golang için tam paketlerdi.
      QR kodlarla ilgili hata düzeltme kısmını öğrenebileceğim faydalı kaynaklar varsa duymak isterim.
  • Daha önce bir Rust uygulaması yapmıştım.
    https://github.com/aabiji/qr
  • İçinde bulunulan yılın yazısı değilse başlığa yazının yılını, burada 2018’i eklemek iyi bir gelenektir.
    • Katılıyorum. Orijinal bağlantıda benim gördüğüm kadarıyla tarih yoktu ve artık düzenleyemiyorum.
  • Güzel. QR kodların nasıl çalıştığını öğrenmek uzun zamandır yapılacaklar listemdeydi; iyi bir giriş yazısı oldu.
  • Artık nasıl çalıştığını bildiğimize göre SQL sorgularında da kullanabiliriz: https://github.com/Florents-Tselai/pgQR