QR kodun 30%-i yox olarsa, telefon onu necə oxuya bilər?

Təsəvvür edin ki, telefonumuzu bir QR koduna tuturuq. Kodun bir hissəsi cızılıb. Bəzi qara kvadratlar isə tamamilə yox olub. Amma telefon yenə də QR kodu oxuyur.

Bəs telefon orada olmayan məlumatı haradan tapır və kodu necə açır?

Bu sualın cavabı bizi Reed–Solomon alqoritminə gətirib çıxarır. Burada söhbət sadəcə “QR kodu xilas edən bir alqoritm”dən getmir.

Əslində qarşımızda daha fundamental bir fikir dayanır:

Bir mesajın müəyyən hissəsi pozularsa, qalan məlumatlardan istifadə edərək onu yenidən bərpa etmək mümkündürmü?

Bu problem demək olar ki, kompüterlərin fiziki dünya ilə əlaqə saxladığı, hər yerdə qarşımıza çıxır.

Məsələn:

1. CD-nin səthində müəyyən cızıqlar yarana bilər.

2. Hansısa məlumat daşıyıcısında bəzi bitlər pozula bilər.

3. Rabitə kanalı vasitəsilə göndərilən simvollar səs-küy səbəbindən dəyişə bilər.

4. Kosmik aparatdan Yerə göndərilən məlumat milyardlarla kilometrlik yol boyunca müxtəlif xətalarla qarşılaşa bilər.

Bu zaman kompüter belə bir sualla üzləşir:

“Bu məlumat pozulub. Bəs orijinalı necə idi?”

Reed–Solomon məhz bu zaman köməyə gəllr.

1960-cı illərdə Irving Reed və Gustave Solomon tərəfindən işlənib hazırlanmış bu üsul verilənlərin yanına riyazi olaraq hesablanmış əlavə məlumatlar yerləşdirir.

Bu əlavə məlumatlar verilənlərin sadə surəti deyil. Onlar məlumatın strukturundan yaradılan bir növ riyazi “sübut” rolunu oynayır.

Beləliklə, məlumatın bir hissəsi dəyişdikdə decoder sadəcə:

“Burada xəta var.”

deməklə kifayətlənmir.

Müəyyən şərtlər daxilində o, daha konkret nəticəyə gələ bilir:

“Xəta məhz buradadır və burada olması lazım olan əsl dəyər budur.”

Və bütün bunlar məlumatı başdan-ayağa yenidən kopyalamadan həyata keçirilir.

İndi isə yenidən QR kodlara qayıdaq.

Çünki hər gün gördüyümüz o sadə qara-ağ kvadratların arxasında əslində kifayət qədər maraqlı bir riyazi sistem dayanır.

QR kod necə zədələnə bilər?

Əvvəlcə “xəta” dedikdə nəyi nəzərdə tutduğumuza baxaq.

QR kod fiziki olaraq:

• cızıla bilər;

• çirklənə bilər;

• üzərinə logo və ya başqa bir obyekt yerləşdirilə bilər;

• bəzi modulları tamamilə itə bilər;

• aşağı keyfiyyətli kamera ilə çəkilə bilər;

• perspektiv səbəbi ilə forması təhrif oluna bilər;

İndi isə keçək prosesə.

Prosesi sadələşdirilmiş şəkildə belə təsəvvür edə bilərik:

Kamera görüntüsü
       ↓
QR kodu tap və analiz et
       ↓
Codeword-ləri çıxar
       ↓
Reed–Solomon
       ↓
Xətaları düzəlt
       ↓
Məlumatı oxu

Reed–Solomon görüntünün özünü düzəltmir. O, QR görüntüsündən çıxarılmış məlumatlardakı xətaları düzəltməyə çalışır.

Bəs Reed–Solomon nə əlavə edir?

Tutaq ki, göndərmək istədiyimiz məlumat:

HELLO

olsun.

Encoder bunu sadəcə olduğu kimi göndərmir. Məlumat riyazi simvollar şəklində nəzərdən keçirilir.

Bu simvolları bir polinomun əmsalları kimi düşünə bilərik:

M(X) = a₃X³ + a₂X² + a₁X + a₀

Lakin burada adi ədədlərlə işləmədiyimizi nəzərə almaq vacibdir.

Reed–Solomon Galois Field, yəni sonlu sahə (finite field) adlanan riyazi sistemdən istifadə edir.

QR kodlarda isə məlumat 8 bitlik codeword-lər şəklində təşkil olunur.

Daha sonra encoder-in əsas hissələrindən biri olan generator polynomial işə düşür.

Sadələşdirilmiş şəkildə:

Cₖ(X) = Xⁿ⁻ᵏM(X) mod g(X)

hesablanır.

Burada alınan əlavə hissə xəta düzəltmə üçün istifadə olunan parity məlumatını təşkil edir.

Daha sonra:

C(X) = Xⁿ⁻ᵏM(X) + Cₖ(X)

şəklində codeword yaradılır.

Prosesi belə təsəvvür edə bilərik:

        DATA
         ↓
     Polynomial
         ↓
  Galois Field əməliyyatları
         ↓
   Generator Polynomial
         ↓
       PARITY
         ↓
    DATA + PARITY

Parity məlumatın sadə surəti deyil.

O, məlumatın öz riyazi strukturundan yaradılır. (Sapı özümüzdən olan balta.)

Və decoder sonradan məhz bu riyazi əlaqədən istifadə edərək xətaları müəyyənləşdirir və düzəldir.

İndi mərdimazarlıq edib QR kodu korlaya bilərik.

Göndərilən düzgün codeword-i C(X) ilə işarə edək.

Yolda bəzi simvollar dəyişsin.

Bu halda decoder-ə artıq:

R(X) = C(X) + E(X) -ə

çatır.

Burada:

• C(X) → orijinal codeword;

• E(X) → xəta;

• R(X) → qəbul edilmiş, yəni zədələnmiş codeword.

Məsələn:

Göndərilən:

12  45  83  17  91  24  60
           ↓

Qəbul edilən:

12  45  21  17  91  24  60

Burada decoder-in qarşısında iki əsas sual yaranır:

21-in səhv olduğunu haradan bilirəm?

Və daha vacibi:

Orada 83-ün olmalı olduğunu haradan bilirəm? (maraqlı sualdı)

Reed–Solomon decoder-imiz riyazi Sherlock Holmes çıxır ya da nə bilim bəlkə də kahin.

Decoder cavabı bir anda tapmır. Bunun üçün bir neçə mərhələdən keçir.

1. Syndrome — “Nəsə səhvdir?”

İlk mərhələdə syndrome dəyərləri hesablanır.

Əgər codeword düzgün şəkildə qəbul edilibsə, syndrome-lar gözlənilən nəticəni verir. Reed–Solomon-un standart quruluşunda onlar sıfır olur.

Əgər xəta varsa, sıfırdan fərqli syndrome-lar ortaya çıxır.

2. Error-locator polynomial — “Xəta haradadır?”

Əgər xəta müəyyən edilibsə, növbəti məsələ onun yerini tapmaqdır.

Syndrome-lardan istifadə edilərək error-locator polynomial yaradılır.

Bu polinomun kökləri əsasında hansı mövqelərin səhv olduğu müəyyən edilə bilər.

Məsələn, decoder belə bir nəticəyə gələ bilər:

5-ci simvol  → səhvdir
11-ci simvol → səhvdir

Bu mərhələdə Berlekamp–Massey və Chien Search kimi alqoritmlərdən istifadə oluna bilər.

Beləliklə, decoder artıq bilir ki, problem hansı mövqedədir.( QR code nümunəsi üçün hissələrdə)

3. Error values — “Düzgün dəyər nədir?”

Xətanın yerini tapdıq.

Amma hələ bilmirik ki, həmin mövqedə əslində hansı dəyər olmalı idi.

Decoder bu dəfə syndrome-lardan və tapılmış xəta mövqelərindən istifadə edərək error values-ı hesablayır.

Beləliklə:

Xəta haradadır?
        +
Xətanın dəyəri nədir?
        ↓
Error Pattern

alınır.

Sonra bu xəta pattern-i qəbul edilmiş məlumatdan çıxarılır və düzəldilmiş codeword əldə edilir.

Prosesi qısaca belə düşünək:

ZƏDƏLƏNMİŞ QR
      ↓
Codeword-lər
      ↓
Syndrome-lar
      ↓
Error-locator polynomial
      ↓
Xəta mövqeləri
      ↓
Xəta dəyərləri
      ↓
Xətaları düzəlt
      ↓
ORİJİNAL MƏLUMAT

Bəs itmiş məlumatın nə qədərini xilas etmək mümkündür?

QR Code dörd fərqli xəta düzəltmə səviyyəsi təqdim edir:

Amma burada çox vacib bir detal var:

“30%” QR kodun səthinin 30%-ni istənilən şəkildə bağlaya bilərsiniz demək deyil.

Bu faiz codeword-lərlə bağlı xəta düzəltmə qabiliyyətini ifadə edir. Həmçinin xətanın harada yerləşməsi və onun error kimi, yoxsa erasure kimi qəbul edilməsi də nəticəyə təsir edir.

Buna görə QR kodun ortasına böyük bir logo qoyulduqda onun işləməsinin səbəbi:

“QR kodların 30%-i silinsə də, onlar həmişə işləyir.”

deyil.

Əsas səbəb budur:

QR kodun daxilində məlumatın müəyyən hissəsi zədələndikdə onu bərpa etməyə imkan verən riyazi redundancy mövcuddur.

DENSO WAVE-in rəsmi izahına görə, QR Code-da xəta düzəltmə mexanizmi orijinal məlumatın üzərinə Reed–Solomon Code (error correction data) əlavə edilməsi ilə həyata keçirilir.

Bu günkü blogumuz bu qədər. Əgər bu mövzu sizə çox maraqlı gəldisə, NASA-nın yayımladığı "Tutorial Reed-Solomon error correction coding"- i oxuya bilərsiniz, orda hər şey daha texniki və detallıdır. Nəzərə alsaq ki, 144 səhifədən ibarətdir.