Reed-Solomon Hataları: Dört Delphi 2D Barkod Kodlayıcısı

Üretici polinomunun sabit terimini birinci saklayıp bölmeye baştaki terimden başlayan bir Reed-Solomon kodlayıcı, aslında hiç hata düzeltme hesaplamıyordur. HotPDF tam da bunu dört 2D barkod kodlayıcıda yayınladı — QR, Data Matrix, PDF417 ve Aztec — ve ürettikleri her sembol, uyumlu hiçbir tarayıcının kullanamayacağı bir kontrol bloğu taşıyordu

İlginç olan aritmetik sürçme değil. Yayılma. Bir kodlayıcı önce yazıldı, bölme döngüsü sonraki üçüne kopyalandı ve her yeni format, tek bir yayınlanmış test vektörüne karşı hiç doğrulanmamış bir kusuru miras aldı. Semboller yine de render ediliyordu, finder desenleri doğru yerde oturuyordu, boyutlar doğruydu. Yalnızca bir 2D barkodun bir lekeye dayanmasını sağlayan baytlar çöptü

Dört kodlayıcıya kopyalanan tek bir ters polinom

Kök neden, sentetik bölme döngüsünün içindeki bir saklama sırası uyumsuzluğu. Dört HotPDF kodlayıcı da üretici polinomunu katsayıları düşükten yükseğe kurar; Gen[0] sabit terimi, Gen[High(Gen)] monik baştaki katsayıyı tutar. Bölme döngüsü mesaj üzerinde ilerlerken Gen[J] indeksini ileri doğru kullanıyordu; bu, ters çevrilmiş polinoma bölmekle aritmetik olarak aynı şey. İlkini gizleyen ikinci bir sonuç daha vardı: baştaki katsayı hiçbir zaman I konumuna inmediği için Work[I] hiç temizlenmiyordu, o yüzden bölme aslında hiçbir şeyi indirgemiyordu. Döngü yine de sonlanıyor ve kuyruğu tam doğru uzunlukta bir diziyle dolduruyordu

// HPDFQRCode.pas içinde THPDFQRCode.ComputeEC
Gen := GeneratorPoly(ECCount);            // Gen[0] sabit terimdir
SetLength(Work, Length(Data) + ECCount);
for I := 0 to High(Data) do
  Work[I] := Data[I];
for I := Length(Data) to High(Work) do
  Work[I] := 0;
for I := 0 to High(Data) do
begin
  Factor := Work[I];
  if Factor = 0 then
    Continue;
  // Gen[High(Gen)] Work[I]'yı temizleyen baştaki 1'dir; Gen üzerinde ileri
  // yürümek bunun yerine ters çevrilmiş polinoma böler
  for J := 0 to High(Gen) do
    Work[I + J] := Work[I + J] xor GFMul(Gen[High(Gen) - J], Factor);
end;

Düzeltme tek bir indeks ifadesi: Gen[High(Gen) - J]. Ondan sonra THPDFQRCode.ComputeEC, ISO/IEC 18004 §7.5'teki çalışılmış örneği birebir üretir: sürüm 1-M bayt modu bloğu 32 91 11 120 209 114 220 77 67 64 236 17 236 17 236 17, on kontrol sözcüğü 196 35 39 119 235 215 231 226 93 23 verir. Bu tek bir iddiadır ve daha ilk gün başarısız olurdu

Aztec sembolü neden yükünü de kaybetti?

Aztec aynı hatanın daha ağır bir sürümünü taşıyordu, çünkü TAztecGF.Encode yerinde böler. Rutin, mesajı ve ardından sıfırlanmış kontrol sözcüğü yuvalarını tutan Words alır ve çağıran o dizinin tamamını sembole yazar. Polinom bölme, indirgerken bölüneni yok eder; o yüzden döngü gerçekten indirgemek üzere düzeltildiğinde mesaj sözcükleri yol boyunca üzerine yazılıyordu. Hem yük hem mod mesajı bozuk çıkıyordu; bozuk sürümün hiçbir şeyi indirgemeyerek kazara önlediği bir başarısızlık bu

// HPDFAztec.pas içinde TAztecGF.Encode
SetLength(Message, DataCount);
for I := 0 to DataCount - 1 do
  Message[I] := Words[I];
for I := 0 to DataCount - 1 do
begin
  Factor := Words[I];
  if Factor = 0 then
    Continue;
  for J := 0 to ECCount do
    Words[I + J] := Words[I + J] xor Multiply(Gen[ECCount - J], Factor);
end;
// Bölme mesaj bölgesini temizler ama çağıran dizinin tamamını
// sembole yazar, o yüzden veri sözcükleri geri dönmeli
for I := 0 to DataCount - 1 do
  Words[I] := Message[I];

Aztec iki farklı alan kullanır ve regresyon fikstürü ikisini de çalıştırır. GF(64) içinde — ilkel polinom $43 üzerine kurulu altı bitlik bir sembolün alanı — 12 45 3 sözcükleri beş kontrol sözcüğüyle 41 32 26 33 23 üretirken baştaki üçü dokunulmadan kalır. GF(16) içinde — ilkel polinom $13 ile mod mesajının alanı — 5 9 sözcükleri 11 15 6 8 üretir. İkisi de HPDFAztecTestEncode kancası üzerinden ISO/IEC 24778'ye karşı çalışır

Data Matrix neden bir yerine iki düzeltme gerektiriyor?

THPDFDataMatrix.ComputeEC, ortak hatanın üstüne ikinci ve bağımsız bir hata bindirmişti: üretici polinomunu kökleri α^0'dan başlayacak şekilde kuruyordu, oysa ISO/IEC 16022 Ek E köklerin α^1'den başlamasını şart koşar. Yalnızca bölme indeksini düzeltmek, standart örnek için 146 107 90 179 128 kontrol sözcüklerini verir; bunlar doğruları kadar makul görünür ve yine de okunamaz durumdadır. Sayılar eşleşmeden önce iki kusurun da gitmesi gerekiyordu

// HPDFDataMatrix.pas içinde THPDFDataMatrix.ComputeEC
Gen[0] := 1;
for I := 0 to ECCount - 1 do
begin
  // DMExp[I + 1]: kökler alpha^0'dan değil alpha^1..alpha^ECCount aralığında ilerler
  for J := ECCount downto 1 do
    Gen[J] := GFMul(Gen[J], DMExp[I + 1]) xor Gen[J - 1];
  Gen[0] := GFMul(Gen[0], DMExp[I + 1]);
end;

Referans noktası bir yoruma sığacak kadar küçük. '123456' dizesi 142 164 186 ASCII kod sözcüklerine kodlanır, 10x10 bir sembol beş kontrol sözcüğü taşır ve doğru blok 114 25 5 88 102'dir. HPDFDataMatrixTestComputeEC, {$IFDEF HPDF_TESTING} kapısının arkasındaki sınıf fonksiyonunu açığa çıkarır; o yüzden fikstür, bir kodlayıcı başlatmadan ya da bir sayfa render etmeden bu beş değeri iddia eder. Galois alanının kendisi — InitDMTables tarafından ilkel polinom $12D üzerinden DMExp ve DMLog tablolarına kurulan — en başından doğruydu; hatanın bu kadar iyi saklanmasının nedeni tam da bu

PDF417, işaretlerin önemli olduğu bir asal alan üzerinde böler

PDF417 tek yerine dört değişiklik gerektiriyordu, çünkü GF(929) bir asal alandır, ikili genişleme alanı değil: toplama xor değildir, çıkarma toplama değildir ve her üretici faktörünün işareti bir gösterim değil, gerçek aritmetiktir. Her faktör (x - 3^i) olmalıdır; kodda bu, 929 - GF929Pow(3, I) ile çarpmak demektir; indirgeme adımı çıkarmalıdır; kökler ISO/IEC 15438 §5.5'e göre 3^1'den başlar; ve Factor, iç döngü çalışmadan önce bir yerele kilitlenmelidir, çünkü J = 0 geçişi Work[I] değerini yazar ve aksi halde çarpanı kendi altında değiştirir. HPDFPDF417TestComputeEC düzeltilmiş sonucu sabitler: 5 453 178 121 239 kod sözcükleri dört hata düzeltme sözcüğüyle 452 327 657 619 verir

// HPDFPDF417.pas içinde THPDFPDF417.ComputeEC
for I := 1 to ECCount do
begin
  Root := (929 - GF929Pow(3, I)) mod 929;   // faktör (x - 3^i)
  for J := ECCount downto 1 do
    Gen[J] := (GF929Mul(Gen[J], Root) + Gen[J - 1]) mod 929;
  Gen[0] := GF929Mul(Gen[0], Root);
end;
// ...
Factor := Work[I];                          // kilit: J = 0, Work[I] değerini yeniden yazar
if Factor = 0 then
  Continue;
for J := 0 to ECCount do
  Work[I + J] := (Work[I + J] + 929 - GF929Mul(Gen[ECCount - J], Factor)) mod 929;

Data Matrix finder'ı ters yüz kurulmuştu

Doğru kontrol sözcükleri, finder deseni yansıtılmış bir sembolü kurtarmaz ve aynı sürüm bunu da düzeltmek zorundaydı. Yerleştirme kodu dolu bir sol sütun, dolu bir sağ sütun ve üst ile alt satırlar boyunca değişen modüller çiziyordu; oysa ISO/IEC 16022 §5.2 dolu bir sol sütun artı dolu bir alt satır ister — L şeklindeki finder — değişen saat izi de üst satır ve sağ sütun boyunca uzanır. Bunu ters yapmayı kolaylaştıran şey koordinat kuralı: HotPDF modül satırlarını Y + I * ModuleSize ile render eder; bu, sol-üst köşe başlangıç anlamıdır; o yüzden Modules[Size - 1, *] basılan sembolün alt satırıdır. Y'nin yukarı doğru büyüdüğü PDF kullanıcı uzayında akıl yürüten herkes, dolu bacağı yanlış tarafa koyar ve ekranda hiçbir şüphe uyandıran şey görmez

Dört bozuk kodlayıcı neden yıllarca testleri geçti?

Çünkü testler yapıyı iddia ediyordu, kusurlar aritmetikteydi. Mevcut QR, Data Matrix ve Aztec durumları finder modüllerini, zamanlama desenlerini ve sembol boyutlarını kontrol ediyordu; hepsi gerçekten doğruydu; hiçbir test bir kontrol sözcüğünü yayınlanmış bir vektörle karşılaştırmamıştı. İkinci neden daha da genelleşiyor. HotPDF yerleşik bir QR decoder'ıyla gelir ve onu kodlayıcıyı doğrulamak için kullanmak apaçık bir round trip gibi görünür; ancak bu decoder veri kod sözcüklerini okur ve hiç Reed-Solomon düzeltmesi yapmaz, o yüzden kodlayıcının yazdığının aynısını geri okur ve başarı raporlar. Bir kodlayıcı ile bir decoder aynı varsayımı paylaştığında, round trip testi ikisinin aynı fikirde olduğunu kanıtlar, ikisinden birinin doğru olduğunu değil. Bir hata düzelten kod, standartta basılı vektörlere karşı doğrulanmalı, asla kendi decoder'ına karşı değil. THPDFBarcodeECCTests fikstürü artık her format için bir test tutuyor; her biri neyi sabitlediğiyle adlandırılıyor ve her biri aritmetiğe yalnızca {$IFDEF HPDF_TESTING} altında derlenen bir kanca üzerinden ulaşıyor:

• QRCheckWordsMatchISO18004Example, sürüm 1-M bayt modu örneğinin on kontrol sözcüğünü iddia eder
• DataMatrixCheckWordsMatchISO16022Example, 142 164 186 kod sözcükleri için 114 25 5 88 102 değerini iddia eder
• PDF417CheckWordsMatchGF929Reference, GF(929) üzerinde 3^1'den 3^4'e köklerle 452 327 657 619 değerini iddia eder
• AztecCheckWordsKeepMessageAndMatchReference, kontrol sözcüklerini ve mesaj sözcüklerinin yerinde bölmeden sağ çıktığını iddia eder

Dört soru, bakımını yaptığın herhangi bir kodlayıcıda bu ailenin çoğunu yakalar. Üretici saklama sıran, bölme indeks sıranla eşleşiyor mu ve bunu kanıtlayan satırı gösterebiliyor musun? Kökler standardın söylediği yerde mi başlıyor — Data Matrix için α^1, PDF417 için 3^1? Yerinde bir bölme, mesaj bölgesini sonrasında geri getiriyor mu? En az bir test, modül sayıları yerine kontrol sözcüklerini bir şartnamede basılı bir sayıyla karşılaştırıyor mu? Mevcut eserlere ne yapacağına karar verirken kapsam da önemli. v2.748.0'dan önce üretilen semboller render ediliyor ve ideal koşullarda sık sık taranıyor, çünkü temiz bir görüntü okunmak için düzeltme gerektirmez; kaybettikleri şey, bu formatları seçmenin bütün nedeni olan hasar toleransı. Uzun ömürlü etiketler ve etkilenen semboller taşıyan arşivlenmiş belgeler, telefon kamerasıyla nokta kontrolü yapmaktansa yeniden üretilmeye değer. Kodlayıcılar, HotPDF içindeki barkod desteğinde, QR çözme yolu ve yönelim işlemesi ile sembolleri sayfaya yerleştiren rapor çıktı katmanının yanında yer alır; eksiksiz barkod API referansı, Delphi ve C++Builder için HotPDF Delphi Component ile birlikte gelir