Kódování QR kódů

Autor: Bc. Luděk Reif

Souhrn informací o QR kódu

a

ukázka Reed-Solomonova kódování

1. listopad 2013

Historie QR kódů

Snímek 2 z 14 1. listopad 2013

• Nástupce čárových kódů • Větší množství informace

• Stále potřeba přímá viditelnost

• Levné řešení

• Alternativní technologie

• RFID • nepotřebuje přímou viditelnost

• výrazně dražší řešení

Specifikace QR kódů

Snímek 3 z 14 1. listopad 2013

• Mnohem více informací než čárové kódy

• Standardní ve 40 (1 až 40) velikostech

• Velikost podle vzorce: 17 + (v x 4)

• Nejmenší kódy 21x21, největší 177x177

• Navíc Micro QR kód (11x11 až 17x17)

• Kapacita

• 7 089 číslic

• 4 296 písmen a číslic

• 2 953 8-bitových data

• 1 817 znaků kandži (japonské znaky)

Specifikace QR kódů II

Snímek 4 z 14 1. listopad 2013

• Čtyři úrovně korekce (redundance)

• Úroveň L – až 7% poškozené plochy

• Úroveň M – až 15% poškozené plochy

• Úroveň Q – až 25% poškozené plochy

• Úroveň H – až 30% poškozené plochy

Úroveň L

Text „Hello, World!“

Úroveň H

Geometrická vrstva

Snímek 5 z 14 1. listopad 2013

• Klidová zóna minimálně 4 body okolo kódu

• Čtverce (3) určující pozici (Č 7x7 + B 5x5 + Č 3x3) s bílou okolo

• Další (0 - 46) čtverce (Č 3x3 + B 2x2 + Č 1x1) doplňují zarovnání

• Na 7. řádku a 7. sloupci časovací znaky (střídavě Č a B)

Geometrická vrstva II

Snímek 6 z 14 1. listopad 2013

v Strana Plocha Pozice Časování Verze A Zarovnání Pro data Vzdál. zarovnání

1 21 441 192 10 0 0 0 239 -

10 57 3 249 192 82 36 2 140 2 799 22

20 97 9 409 192 162 36 3 305 8 714 28

30 137 18 769 192 242 36 5 785 17 514 26

40 177 31 329 192 322 36 6 1100 29 679 28

Tabulka s příklady verzi QR kódu (počty bodů)

Ukázka složitého QR kódu

Snímek 7 z 14 1. listopad 2013

Recept na svíčkovou o 1 053 českých znacích

úroveň zabezpečení L, rozměr 113x113 (verze 24)

Informační vrstva

Černý bod = binární 1 Bílý bod = binární 0

• Plnění začíná v pravém dolním rohu dvojřad

• Po naplnění se směr otáčí zase ve dvojřadu

• Pokud narazí na formátovací prvek, tak jej přeskočí (zarovnání, časování) nebo se odrazí (pozice)

• Svislé časování je přeskočeno, dokončí se plnění posledními třemi dvojřady a končí v levém spodním rohu

• Data obsahují bytovou zprávu a korekční byty

• Prvotní nemaskovaná data jsou uložena postupně

• Nejprve data, poté korekční kód

Snímek 8 z 14 1. listopad 2013

Informační vrstva II

• Maskování • V kódu mohou vznikat vzory matoucí geometrickou vrstvu

• Tři bity označují způsob maskování pro celou informační vrstvu

• Maskuje se podle výsledku maskování, které dostane nejméně záporných bodů

• Informace o korekci • Dva bity označují úroveň korekce (tabulka pro 26 bytový blok dat)

Úroveň korekce Bitové označení Počet korekčních bytů Počet datových bytů

L 01 7 19

M 00 10 16

Q 11 13 13

H 10 17 9

Snímek 9 z 14 1. listopad 2013

Informační vrstva III

Zbývajících 10 bitů obsahuje samoopravné kódy formátu

Všechny formátovací informace jsou na kódu dvakrát

Informace jsou kódovány pomocí BCH kódů - kódovaná část se převede na polynom

- násobí se kódovacím polynom

- modulo řídící polynom nad 𝑍2

- výsledkem je zakódovaná část dat

Data jsou kódovány pomocí Reed- Solomonových kódů

- kódy jsou speciálním případem BCH kódů

- symbolově orientovány (kódování po celých slovech)

- předpokládají shlukové chyby

Snímek 10 z 14 1. listopad 2013

Příklad vytvoření QR kódu

1. Vstupní řetězec přepsaný podle tabulky

MARTINS = (22,10,27,29,18,23,28)

(22,10) (27,29) (18,23) (28)

2. Rozdělit na skupiny po dvou dekadických číslech

C1 = 22*45 + 10 = 1 000

C2 = 27*45 + 29 = 1244

C3 = 18*45 + 23 = 833

C4 = 28

3. Operace podle vzorce C = A*45 + B

1 000 = 011 1110 1000

1255 = 100 1101 1100

833 = 011 0100 0001

28 = 01 1100

4. Dekadická čísla na binární (11bit + poslední 6bit)

5. Spojit na jedno číslo

01111101000 10011011100 01101000001 011100

6. Určí se indikátor vstupných dat

Pro alfanumerické řetězce: 0010

7. počet vstupních symbolů ve dvojkové soustavě

000000111

8. Vše do jednoho řetězce

0010 000000111 01111101000 10011011100 01101000001 011100

Každých osm bitů představuje 1 CW (blok dat u QR), bude tedy 7 CW

Korekce je typu L, rozložení data : korekce bude tedy 13 CW na 13 CW

9. Do nevyužitých CW se doplní vyplňující CW

Liché: 11101100 Sudé: 00010001

10. Dopočítá se korekce a využije se maska dat

11. Doplní se informace o korekci a masce

Pomocí BCH dostaneme 10 1100 1000

Využije se Reed-Solomonova kódování

Snímek 11 z 14 1. listopad 2013

Příklad vytvoření QR

Informační vrstva V

Snímek 12 z 14 1. listopad 2013

Původní binární data

00010000 00100000 00001100 01010110 01100001 10000000 11101100 00010001 11101100 00010001 11101100 00010001 11101100 00010001 11101100 00010001

(128 bitů)

Zakódovaná data Reed-Solomonovým kódováním

00010000 00100000 00001100 01010110 01100001 10000000 11101100 00010001 11101100 00010001 11101100 00010001 11101100 00010001 11101100 00010001 10100101 00100100

11010100 11000001 11101101 00110110 11000111 10000111 00101100 01010101

(208 bitů)

korekce typu M – lze opravit až 15% chyb

Reed-Solomonovo kódování II

Příklad polynomu pro generování Reed-Solomonova kódu

𝑔 𝑥 = 𝑥5 + 31𝑥4 + 198𝑥3 + 63𝑥2 + 147𝑥 + 116𝑥0

Polynom pro generování se liší podle použité verze. Původní data se převedou na mnohočlen (kódována po bytových blocích).

Např. 255 128 10 155:

𝑝 𝑥 = 255𝑥8 + 128𝑥7 + 10𝑥6 + 155𝑥5 + 0𝑥4 + 0𝑥3 + 0𝑥2 + 0𝑥1 + 0𝑥0

𝒙 s exponenty 0 až 4 se dopočítávají při kódování a zde jsou pouze pro doplnění. Pro zvolené kódování jsou doplněny 4 členy. Jejich počet mění podle verze.

Snímek 12 z 14 1. listopad 2013

𝒙𝟓 𝟑𝟏𝒙𝟒 𝟏𝟗𝟖𝒙𝟑 𝟔𝟑𝒙𝟐 𝟏𝟒𝟕𝒙 𝟏𝟏𝟔𝒙𝟎

𝜶𝟎 𝜶𝟏𝟏𝟑 𝜶𝟏𝟔𝟒 𝜶𝟏𝟔𝟔 𝜶𝟏𝟏𝟗 𝜶𝟏𝟎

Reed-Solomonovo kódování III

Příklad kódování Vstupní data: 1 (00000001)

𝑔 𝑥 = 𝑥2 + 3𝑥 + 2𝑥0

Výsledná data: 3 2 (00000011 00000010)

Snímek 12 z 14 1. listopad 2013

𝒙𝟐 𝟑𝒙 𝟐𝒙𝟎

𝜶𝟎 𝜶𝟐𝟓 𝜶𝟏

1x2+ 0x1+ 0x0

α0

g(x)*(α0)*x0 0 + 0 =α0

xor 1 = 0

25 + 0 = α25

xor 0 = 3

1 + 0 = α1

xor 0 = 2

3x1+ 2x0

α25 α1

Děkuji za pozornost

Snímek 13 z 14 1. listopad 2013

Zdroje

- https://cs.wikipedia.org/wiki/QR_k%C3%B3d

- http://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders

- http://access.feld.cvut.cz/view.php?cisloclanku=2006080002

- http://zin.tym.cz/index.php?k=0501&s=42

- http://www.vutbr.cz/www_base/zav_prace_soubor_verejne.php?file_id=29510

- http://www.pclviewer.com/rs2/calculator.html

Snímek 14 z 14 1. listopad 2013