Aztec -kode - Aztec Code

Kodning: "Dette er et eksempel Aztec -symbol for Wikipedia."

Aztec Code er en type 2D -stregkode, der blev opfundet af Andrew Longacre, Jr. og Robert Hussey i 1995. Koden blev udgivet af AIM, Inc. i 1997. Selvom Aztec -koden blev patenteret, blev dette patent officielt offentligt ejet. Aztec -koden udgives også som ISO/IEC 24778: 2008 -standard. Opkaldt efter ligheden mellem det centrale findermønster og en aztekisk pyramide , har aztekisk kode potentiale til at bruge mindre plads end andre matrixstregkoder, fordi den ikke kræver en omgivende blank "stille zone".

Struktur

Symbolet er bygget på et firkantet gitter med et bulls-eye mønster i midten for at lokalisere koden. Data er indkodet i koncentriske firkantede ringe omkring bulls-eye-mønsteret. Det centrale bulls-eye er 9 × 9 eller 13 × 13 pixels , og en række pixels omkring det, der koder for grundlæggende kodningsparametre, hvilket producerer en "kerne" på 11 × 11 eller 15 × 15 firkanter. Data tilføjes i "lag", der hver indeholder to ringe med pixels, hvilket giver en total størrelse på 15 × 15, 19 × 19, 23 × 23 osv.

Hjørnens hjørner indeholder orienteringsmærker, så koden kan læses, hvis den roteres eller reflekteres. Afkodning begynder ved hjørnet med tre sorte pixels og fortsætter med uret til hjørnerne med to, et og nul sorte pixels. De variable pixels i den centrale kerne koder størrelsen, så det er ikke nødvendigt at markere grænsen for koden med en tom "stille zone", selvom nogle stregkodelæsere kræver en.

• 

  Kernen i den kompakte aztekiske kode (rød stigende diagonal ruge), der viser det centrale bulls-eye, de fire orienteringsmærker (blå diagonal krydskravning) og plads til 28 bits (7 bits pr. Side) kodende oplysninger (grøn vandret udklækning). Den første ring med data begynder uden for den (grå faldende diagonal udklækning).

• 

  Kernen i den fulde aztekiske kode. 40 bits er tilgængelige mellem orienteringsmærkerne for kodningsparametre.

• 

  Beskeddata placeres i et spiralmønster omkring kernen. Tilstandsmeddelelsen begynder "01011100", hvilket angiver 01₂+1 = 2 lag og 011100₂+1 = 29 datakodeord (med 6 bits hver).

Den kompakte Aztec -kodekerne kan være omgivet af 1 til 4 lag, der producerer symboler fra 15 × 15 (plads til 13 cifre eller 12 bogstaver) til 27 × 27. Der er desuden en særlig 11 × 11 "rune", der koder for en byte information. Den fulde kerne understøtter op til 32 lag, 151 × 151 pixels, som kan kode 3832 cifre, 3067 bogstaver eller 1914 byte data.

Uanset hvilken del af symbolet, der ikke bruges til de grundlæggende data, bruges det til fejlkorrektion af Reed -Solomon , og opdelingen er fuldstændigt konfigurerbar mellem grænserne for 1 dataord og 3 kontrolord. Det anbefalede antal kontrolord er 23% af symbolkapaciteten plus 3 kodeord.

Aztec Code formodes at producere læsbare koder med forskellige printerteknologier. Det er også velegnet til displays af mobiltelefoner og andre mobile enheder.

Indkodning

Kodningsprocessen består af følgende trin:

1. Konvertering af kildebeskeden til en række bits
2. Beregning af den nødvendige symbolstørrelse og tilstandsmeddelelse, som bestemmer størrelsen på Reed -Solomon kodeordet
3. Bit-fylder beskeden ind i Reed-Solomon kodeord
4. Padding af meddelelsen til en kodeordgrænse
5. Tilføjelse af tjekkodeord
6. Arrangerer det fulde budskab i en spiral omkring kernen

Al konvertering mellem bitstrenge og andre former udføres i henhold til big-endian- konventionen (mest signifikante bit først).

Tegnsæt

Alle 8-bit værdier kan kodes plus to flugtkoder:

• FNC1, et flugtsymbol, der bruges til at markere tilstedeværelsen af ​​en applikationsidentifikator på samme måde som i GS1-128- standarden.
• ECI, en flugt efterfulgt af en 6-cifret udvidet kanaltolkningskode , som angiver det tegnsæt, der bruges til at fortolke følgende bytes.

Som standard fortolkes koderne 0–127 i henhold til ANSI X3.4 ( ASCII ), og 128–255 fortolkes i henhold til ISO 8859-1 : Latin Alphabet No. 1. Dette svarer til ECI 000003.

Bytes oversættes til 4- og 5-bit koder, baseret på en aktuel dekodningstilstand, med skift- og låsekoder til skiftende tilstande. Byteværdier, der ikke er tilgængelige på denne måde, kan blive kodet ved hjælp af en generel "binær skift" -kode, som efterfølges af en længde og et antal 8-bit koder.

Ved ændring af tilstande påvirker et skift kun fortolkningen af ​​den følgende kode, mens en lås påvirker alle følgende koder. De fleste tilstande bruger 5-bit koder, men Digit-tilstand bruger 4-bit koder.

• Indledende tilstand er "Øvre"
• x/S = Skift til tilstand x for et tegn; B/S = skift til 8-bit binær
• x/L = Latch til mode x for følgende tegn
• Punkteringskoder 2-5 koder to bytes hver
• Tabellen viser ASCII-tegn, men det er byteværdierne, der er kodet, selvom et ikke-ASCII-tegn tog det i brug

B/S (binært skift) efterfølges af en 5-bit længde. Hvis den ikke er nul, angiver dette, at 1–31 8-bit bytes følger. Hvis nul, 11 ekstra længde bits koder antallet af følgende bytes mindre 31. (Bemærk, at for 32–62 bytes er to 5-bit bytes skift-sekvenser mere kompakte end en 11-bit.) I slutningen af ​​den binære sekvens, den forrige tilstand genoptages.

FLG ( n ) efterfølges af en 3-bit n værdi. n = 0 koder FNC1. n = 1-6 efterfølges af 1-6 cifre (i cifretilstand), der er nulpolstret for at lave en 6-bit ECI-identifikator. n = 7 er reserveret og i øjeblikket ulovligt.

Tilstandsmeddelelse

Tilstandsmeddelelsen koder for antallet af lag ( L -lag kodet som heltal L −1) og antallet af datakodeord ( D -kodeord, kodet som heltal D −1) i meddelelsen. Alle resterende kodeord bruges som tjekkodeord.

For kompakte Aztec-koder er antallet af lag kodet som en 2-bit værdi og antallet af datakodeord som en 6-bit værdi, hvilket resulterer i et 8-bit modeord. For fulde Aztec-koder er antallet af lag kodet i 5 bits, og antallet af datakodeord er kodet i 11 bits, hvilket giver et 16-bit modeord.

Modeordet er opdelt i 2 eller 4 4-bit kodeord i GF (16) , og 5 eller 6 Reed – Solomon-tjekord tilføjes, hvilket giver en 28- eller 40-bit tilstandsmeddelelse, som er pakket ind i en 1-pixel lag omkring kernen.

Fordi en L+1-lags kompakt Aztec-kode kan indeholde flere data end en L-lags fuld kode, bruges sjældent fulde koder med mindre end 4 lag.

Vigtigst er det, at antallet af lag bestemmer størrelsen på de anvendte kodeord Reed - Solomon. Dette varierer fra 6 til 12 bits:

Kodeordets størrelse b er det mindste lige tal, der sikrer, at det samlede antal kodeord i symbolet er mindre end grænsen på 2 ^b −1, som kan korrigeres med en Reed -Solomon -kode.

Som nævnt ovenfor anbefales det, at mindst 23% af de tilgængelige kodeord plus 3 er forbeholdt korrektion, og der vælges en symbolstørrelse, så meddelelsen passer ind i den ledige plads.

Lidt fyld

Databitene er opdelt i kodeord, hvor den første bit svarer til den mest signifikante koefficient. Mens du gør dette, undgås kodeord for alle-nul og alle-en ved bitfyldning : Hvis de første b -1 bit i et kodeord har den samme værdi, indsættes en ekstra bit med den komplementære værdi i datastrømmen. Denne indsættelse finder sted, uanset om den sidste bit af kodeordet ville have haft den samme værdi eller ej.

Bemærk også, at dette kun gælder for strenge af b −1 bits i begyndelsen af ​​et kodeord . Længere strenge af identiske bits er tilladt, så længe de grænser op til et kodeord.

Ved afkodning kan et kodeord på hele nul eller alt det ene antages at være en sletning og korrigeret mere effektivt end en generel fejl.

Denne proces gør meddelelsen længere, og det endelige antal datakodeord, der er registreret i tilstandsmeddelelsen, kendes ikke, før den er fuldført. I sjældne tilfælde kan det være nødvendigt at springe til det næststørste symbol og starte processen forfra for at opretholde den minimale brøkdel af kontrolord.

Polstring

Efter bitfyldning fyldes datastrengen til den næste kodeordgrænse ved at tilføje 1 bits. Hvis dette ville resultere i et kodeord af alle dem, ændres den sidste bit til nul (og ignoreres af dekoderen som en bitfyldningsbit). Ved afkodning kan polstringsbitene afkodes som skift- og låsekoder, men det påvirker ikke beskedindholdet. Læseren skal acceptere og ignorere en delvis kode i slutningen af ​​meddelelsen, så længe det er alle-en.

Hvis det samlede antal databit, der er tilgængelige i symbolet, ikke er et multiplum af kodeordstørrelsen, forefindes datastrengen med et passende antal 0 bits til at optage den ekstra plads. Disse bits er ikke inkluderet i kontrolordberegningen.

Tjek kodeord

Både tilstandsordet og dataene skal have tilføjede tjekord for at udfylde den ledige plads. Dette beregnes ved at tilføje K -checkord, således at hele meddelelsen er et multiplum af Reed -Solomon -polynomet ( x −2) ( x −4) ... ( x −2 ^K ).

Bemærk, at tjekord ikke er genstand for bitfyldning og kan være alle-nul eller alle-et. Det er således ikke muligt at registrere sletning af et kontrolord.

Lægger beskeden op

9-lags (53 × 53) Aztec-kode, der viser referencegitter.

Et fuldt aztekisk kodesymbol har ud over kernen et "referencegitter" med skiftevis sorte og hvide pixels, der indtager hver 16. række og kolonne. Disse kendte pixels giver en læser mulighed for at opretholde tilpasning til pixelgitteret over store symboler. For op til 4 lag (31 × 31 pixels) består dette kun af enkelte linjer, der strækker sig udad fra kernen og fortsætter det skiftevis mønster. Inde i det 5. lag indsættes dog yderligere rækker og kolonner med skiftevis pixel ± 16 pixels fra midten, så det 5. lag er placeret ± 17 og ± 18 pixels fra midten, og et 5-lags symbol er 37 × 37 pixels .

På samme måde indsættes yderligere referenceretningsrækker og -kolonner ± 32 pixels fra midten, hvilket giver et symbol på 12 lag 67 × 67 pixels. I dette tilfælde optager det 12. lag ringe ± 31 og ± 33 pixels fra midten. Mønsteret fortsætter på ubestemt tid udad, med blokke af 15 pixel data adskilt af rækker og kolonner i referencegitteret.

En måde at konstruere symbolet på er at slette referencegitteret helt og begynde med en 14 × 14-pixelkerne centreret om en 2 × 2 pixel hvid firkant. Del den derefter i 15 × 15 pixelblokke, og indsæt referencegitteret mellem dem.

Tilstandsmeddelelsen begynder i øverste venstre hjørne af kernen og vikles rundt om den med uret i et 1-bit tykt lag. Det begynder med den mest betydningsfulde bit af antallet af lag og slutter med kontrolordene. For en kompakt Aztec-kode brød den i fire 7-bit stykker for at efterlade plads til orienteringsmærkerne. For en fuld aztekisk kode er den opdelt i fire 10-bit stykker, og disse stykker deles hver i to med referencegitteret.

I nogle tilfælde deles matrixens samlede kapacitet ikke jævnt med fulde kodeord. I sådanne tilfælde er hovedmeddelelsen polstret med 0 bits i begyndelsen. Disse bits er ikke inkluderet i kontrolordberegningen og skal springes over under afkodning. Den samlede matrixkapacitet for et fuldt symbol kan beregnes som (112+16*L)*L for en fuld aztekisk kode og (88+16*L)*L for en kompakt aztekisk kode, hvor L er symbolstørrelsen i lag . Som et eksempel er den samlede matrixkapacitet for en kompakt Aztec -kode med 1 lag 104 bit. Da kodeord er seks bits, giver dette 17 kodeord og to ekstra bits. To nul bits er forberedt til meddelelsen som polstring og skal springes over under afkodning.

Den polstrede hovedmeddelelse begynder øverst til venstre på hele symbolet og spiraler rundt om det mod uret i et 2-bit tykt lag, der ender direkte over det øverste venstre hjørne af kernen. Dette placerer de bitfyldte dataord, for hvilke sletninger kan detekteres, i symbolets yderste lag, hvilket er mest tilbøjeligt til sletninger. Checkordene gemmes tættere på kernen. Det sidste kontrolord ender lige over det øverste venstre hjørne af tyrens øje.

Med kernen i sin standardretning placeres den første bit af det første dataord i øverste venstre hjørne, med yderligere bits placeret i en 2-bit bred kolonne fra venstre til højre og top-til-bund. Dette fortsætter indtil 2 rækker fra bunden af ​​symbolet, når mønsteret roterer 90 grader mod uret og fortsætter i en 2-bit høj række, fra bund til top og fra venstre til højre. Efter 4 lige store kvarterlag fortsætter spiralen med det øverste venstre hjørne af det næste indre lag og ender til sidst med en pixel over det øverste venstre hjørne af kernen.

Endelig udskrives 1 bits som sorte firkanter, og 0 bits udskrives som hvide firkanter.

Anvendelse

Online billet af Deutsche Bahn. Bemærk, at Aztec -stregkoden i denne prøvebillet ikke kan læses med en normal app, fordi midten er anderledes.

Transportere

Aztec -koder bruges i vid udstrækning til transportbilletter.

Aztec -koden er valgt af luftfartsindustrien ( IATA's BCBP -standard) til elektroniske boardingkort. Flere flyselskaber sender Aztec -koder til passagerernes mobiltelefoner for at fungere som boardingkort. Disse er ofte integreret med apps på passagerers telefoner, herunder Apple Wallet .

Aztec -koder bruges også i jernbaner, herunder af Teheran Metro , Eurostar , Deutsche Bahn , TCDD Taşımacılık , DSB , České dráhy , Slovak Railways , Slovenian Railways , Croatian Railways , Trenitalia , Nederlandse Spoorwegen , PKP Intercity , VR Group , National Rail , Via Rail , Swiss Federal Railways , SNCB og SNCF til billetter solgt online og udskrevet af kunder eller vist på mobiltelefonskærme. Aztec-koden scannes af en håndholdt scanner af personale i toget eller ved drejebordet for at validere billetten.

Statslige

Bilregistreringsdokumenter i Polen er forsynet med et resumé, komprimeret af NRV2E -algoritmen, kodet som Aztec Code. Arbejder pågår for at gøre bilforsikringsselskaber i stand til automatisk at udfylde de relevante oplysninger baseret på digitale fotografier af dokumentet som det første trin i lukningen af ​​en ny forsikringskontrakt.

Federal Tax Service i Rusland koder betalingsoplysninger i skattemeddelelser som aztekisk kode.

Kommerciel

Mange regninger i Canada bruger nu også denne teknologi, herunder EastLink (firma) , Shaw Cable , Bell Aliant og mange flere.

Referencer

eksterne links

• Aztec -kodespecifikation (ISO/IEC 24778: 2008)