The Aztec Code is a matrix code invented by Andrew Longacre, Jr. and Robert Hussey in 1995.[1] The code was published by AIM, Inc. in 1997. Although the Aztec Code was patented, that patent was officially made public domain.[2] The Aztec Code is also published as ISO/IEC 24778:2008 standard. Named after the resemblance of the central finder pattern to an Aztec pyramid, Aztec Code has the potential to use less space than other matrix barcodes because it does not require a surrounding blank "quiet zone".
The symbol is built on a square grid with a bull's-eye pattern at its centre for locating the code. Data is encoded in concentric square rings around the bull's-eye pattern. The central bull's-eye is 9×9 or 13×13 pixels, and one row of pixels around that encodes basic coding parameters, producing a "core" of 11×11 or 15×15 squares. Data is added in "layers", each one containing two rings of pixels, giving total sizes of 15×15, 19×19, 23×23, etc.
The corners of the core include orientation marks, allowing the code to be read if rotated or reflected. Decoding begins at the corner with three black pixels, and proceeds clockwise to the corners with two, one, and zero black pixels. The variable pixels in the central core encode the size, so it is not necessary to mark the boundary of the code with a blank "quiet zone", although some barcode readers require one.
The core of the compact Aztec code (red ascending diagonal hatching), showing the central bull's-eye, the four orientation marks (blue diagonal cross-hatching), and space for 28 bits (7 bits per side) of coding information (green horizontal hatching). The first ring of data begins outside that (grey descending diagonal hatching).
The core of the full Aztec code. 40 bits are available between the orientation marks for encoding parameters.
Message data is placed in a spiral pattern around the core. The mode message begins "01011100", indicating 01₂+1 = 2 layers, and 011100₂+1 = 29 data codewords (of 6 bits each).
The compact Aztec code core may be surrounded by 1 to 4 layers, producing symbols from 15×15 (room for 13 digits or 12 letters) through 27×27. There is additionally a special 11×11 "rune" that encodes one byte of information. The full core supports up to 32 layers, 151×151 pixels, which can encode 3832 digits, 3067 letters, or 1914 bytes of data.
Whatever part of the symbol is not used for the basic data is used for Reed–Solomon error correction, and the split is completely configurable, between limits of 1 data word, and 3 check words. The recommended number of check words is 23% of symbol capacity plus 3 codewords.[3]
Aztec Code is supposed to produce readable codes with various printer technologies. It is also well suited for displays of cell phones and other mobile devices.
Encoding
The encoding process consists of the following steps:
Converting the source message to a string of bits
Computing the necessary symbol size and mode message, which determines the Reed–Solomon codeword size
Bit-stuffing the message into Reed–Solomon codewords
Padding the message to a codeword boundary
Appending check codewords
Arranging the complete message in a spiral around the core
All conversion between bits strings and other forms is performed according to the big-endian (most significant bit first) convention.
Character set
All 8-bit values can be encoded, plus two escape codes:
FNC1, an escape symbol used to mark the presence of an application identifier, in the same way as in the GS1-128 standard.
ECI, an escape followed by a 6-digit Extended Channel Interpretation code, which specifies the character set used to interpret the following bytes.
By default, codes 0–127 are interpreted according to ANSI X3.4 (ASCII), and 128–255 are interpreted according to ISO/IEC 8859-1: Latin Alphabet No. 1. This corresponds to ECI 000003.
Bytes are translated into 4- and 5-bit codes, based on a current decoding mode, with shift and latch codes for changing modes. Byte values not available this way may be encoded using a general "binary shift" code, which is followed by a length and a number of 8-bit codes.
For changing modes, a shift affects only the interpretation of the single following code, while a latch affects all following codes. Most modes use 5-bit codes, but Digit mode uses 4-bit codes.
Aztec code character encoding
Code
Mode
Code
Mode
Upper
Lower
Mixed
Punct
Digit
Upper
Lower
Mixed
Punct
0
P/S
P/S
P/S
FLG(n)
P/S
16
O
o
^\
+
1
SP
SP
SP
CR
SP
17
P
p
^]
,
2
A
a
^A
CR LF
0
18
Q
q
^^
-
3
B
b
^B
. SP
1
19
R
r
^_
.
4
C
c
^C
, SP
2
20
S
s
@
/
5
D
d
^D
: SP
3
21
T
t
\
:
6
E
e
^E
!
4
22
U
u
^
;
7
F
f
^F
"
5
23
V
v
_
<
8
G
g
^G
#
6
24
W
w
`
=
9
H
h
^H
$
7
25
X
x
|
>
10
I
i
^I
%
8
26
Y
y
~
?
11
J
j
^J
&
9
27
Z
z
^?
[
12
K
k
^K
'
,
28
L/L
U/S
L/L
]
13
L
l
^L
(
.
29
M/L
M/L
U/L
{
14
M
m
^M
)
U/L
30
D/L
D/L
P/L
}
15
N
n
^[
*
U/S
31
B/S
B/S
B/S
U/L
Initial mode is "Upper"
x/S = Shift to mode x for one character; B/S = shift to 8-bit binary
x/L = Latch to mode x for following characters
Punct codes 2–5 encode two bytes each
The table lists ASCII characters, but it is the byte values that are encoded, even if a non-ASCII character set is in use
B/S (binary shift) is followed by a 5-bit length. If non-zero, this indicates that 1–31 8-bit bytes follow. If zero, 11 additional length bits encode the number of following bytes less 31. (Note that for 32–62 bytes, two 5-bit byte shift sequences are more compact than one 11-bit.) At the end of the binary sequence, the previous mode is resumed.
FLG(n) is followed by a 3-bit n value. n=0 encodes FNC1. n=1–6 is followed by 1–6 digits (in digit mode) which are zero-padded to make a 6-bit ECI identifier. n=7 is reserved and currently illegal.
Mode message
The mode message encodes the number of layers (L layers encoded as the integer L−1), and the number of data codewords (D codewords, encoded as the integer D−1) in the message. All remaining codewords are used as check codewords.
For compact Aztec codes, the number of layers is encoded as a 2-bit value, and the number of data codewords as a 6-bit value, resulting in an 8-bit mode word. For full Aztec codes, the number of layers is encoded in 5 bits, and the number of data codewords is encoded in 11 bits, making a 16-bit mode word.
The mode word is broken into 2 or 4 4-bit codewords in GF(16), and 5 or 6 Reed–Solomon check words are appended, making a 28- or 40-bit mode message, which is wrapped in a 1-pixel layer around the core.
Because an L+1-layer compact Aztec code can hold more data than an L-layer full code, full codes with less than 4 layers are rarely used.
Most importantly, the number of layers determines the size of the Reed–Solomon codewords used. This varies from 6 to 12 bits:
Aztec code finite field polynomials
Bits
Field
Polynomial
Used for
4
GF(16)
x4+x+1
Mode message
6
GF(64)
x6+x+1
1–2 layers
8
GF(256)
x8+x5+x3+x2+1
3–8 layers
10
GF(1024)
x10+x3+1
9–22 layers
12
GF(4096)
x12+x6+x5+x3+1
23–32 layers
The codeword size b is the smallest even number which ensures that the total number of codewords in the symbol is less than the limit of 2b−1 which can be corrected by a Reed–Solomon code.
As mentioned above, it is recommended that at least 23% of the available codewords, plus 3, are reserved for correction, and a symbol size is chosen such that the message will fit into the available space.
Bit stuffing
The data bits are broken into codewords, with the first bit corresponding to the most significant coefficient. While doing this, code words of all-zero and all-ones are avoided by bit stuffing: if the first b−1 bits of a code word have the same value, an extra bit with the complementary value is inserted into the data stream. This insertion takes place whether or not the last bit of the code word would have had the same value or not.
Also, note that this only applies to strings of b−1 bits at the beginning of a code word. Longer strings of identical bits are permitted as long as they straddle a code word boundary.
When decoding, a code word of all zero or all one may be assumed to be an erasure, and corrected more efficiently than a general error.
This process makes the message longer, and the final number of data codewords recorded in the mode message is not known until it is complete. In rare cases, it may be necessary to jump to the next-largest symbol and begin the process all over again to maintain the minimum fraction of check words.
Padding
After bit stuffing, the data string is padded to the next codeword boundary by appending 1 bit. If this would result in a code word of all ones, the last bit is changed to zero (and will be ignored by the decoder as a bit-stuffing bit). On decoding, the padding bits may be decoded as shift and latch codes, but that will not affect the message content. The reader must accept and ignore a partial code at the end of the message, as long as it is all-ones.
Additionally, if the total number of data bits available in the symbol is not a multiple of the codeword size, the data string is prefixed with an appropriate number of 0 bits to occupy the extra space. These bits are not included in the check word computation.
Check codewords
Both the mode word, and the data, must have check words appended to fill out the available space. This is computed by appending K check words such that the entire message is a multiple of the Reed–Solomon polynomial (x−2)(x−4)...(x−2K).
Note that check words are not subject to bit stuffing, and may be all-zero or all-one. Thus, it is not possible to detect the erasure of a check word.
A full Aztec code symbol has, in addition to the core, a "reference grid" of alternating black and white pixels occupying every 16th row and column. These known pixels allow a reader to maintain alignment with the pixel grid over large symbols. For up to 4 layers (31×31 pixels), this consists only of single lines extending outward from the core, continuing the alternating pattern. Inside the 5th layer, however, additional rows and columns of alternating pixels are inserted ±16 pixels from the center, so the 5th layer is located ±17 and ±18 pixels from the center, and a 5-layer symbol is 37×37 pixels.
Likewise, additional reference grid rows and columns are inserted ±32 pixels from the center, making a 12-layer symbol 67×67 pixels. In this case, the 12th layer occupies rings ±31 and ±33 pixels from the center. The pattern continues indefinitely outward, with 15-pixel blocks of data separated by rows and columns of the reference grid.
One way to construct the symbol is to delete the reference grid entirely and begin with a 14×14-pixel core centered on a 2×2 pixel-white square. Then break it into 15×15 pixel blocks and insert the reference grid between them.
The mode message begins at the top-left corner of the core and wraps around it clockwise in a 1-bit thick layer. It begins with the most significant bit of the number of layers and ends with the check words. For a compact Aztec code, it is broken into four 7-bit pieces to leave room for the orientation marks. For a full Aztec code, it is broken into four 10-bit pieces, and those pieces are each divided in half by the reference grid.
In some cases, the total capacity of the matrix does not divide evenly by full code words. In such cases, the main message is padded with 0 bits in the beginning. These bits are not included in the check word calculation and should be skipped during decoding. The total matrix capacity for a full symbol can be calculated as (112+16*L)*L for a full Aztec code and (88+16*L)*L for a compact Aztec code, where L is the symbol size in layers.[4] As an example, the total matrix capacity of a compact Aztec code with 1 layer is 104 bits. Since code words are six bits, this gives 17 code words and two extra bits. Two zero bits are prepended to the message as padding and must be skipped during decoding.
The padded main message begins at the outer top-left of the entire symbol and spirals around it counterclockwise in a 2-bit thick layer, ending directly above the top-left corner of the core. This places the bit-stuffed data words, for which erasures can be detected, in the outermost layers of the symbol, which are most prone to erasures. The check words are stored closer to the core. The last check word ends just above the top left corner of the bull's eye.
With the core in its standard orientation, the first bit of the first data word is placed in the upper-left corner, with additional bits placed in a 2-bit-wide column left-to-right and top-to-bottom. This continues until 2 rows from the bottom of the symbol when the pattern rotates 90 degrees counterclockwise and continues in a 2-bit high row, bottom-to-top and left-to-right. After 4 equal-sized quarter layers, the spiral continues with the top-left corner of the next-inner layer, finally ending one pixel above the top-left corner of the core.
Finally, 1 bit are printed as black squares, and 0 bits are printed as white squares.
Usage
Online ticket by Deutsche Bahn. Note that the Aztec barcode in this sample ticket is not readable with a normal app because the center is different.
Transport
Aztec codes are widely used for transport ticketing.
The Aztec Code has been selected by the airline industry (IATA'sBCBP standard) for electronic boarding passes. Several airlines send Aztec Codes to passengers' mobile phones to act as boarding passes. These are often integrated with apps on passengers' phones, including Apple Wallet.
Car registration documents in Poland bear a summary, compressed by NRV2E algorithm, encoded as Aztec Code. Works are underway to enable car insurance companies to automatically fill in the relevant information based on digital photographs of the document as the first step of closing a new insurance contract.
In communications and information processing, code is a system of rules to convert information—such as a letter, word, sound, image, or gesture—into another form, sometimes shortened or secret, for communication through a communication channel or storage in a storage medium. An early example is an invention of language, which enabled a person, through speech, to communicate what they thought, saw, heard, or felt to others. But speech limits the range of communication to the distance a voice can carry and limits the audience to those present when the speech is uttered. The invention of writing, which converted spoken language into visual symbols, extended the range of communication across space and time.
In information theory and coding theory with applications in computer science and telecommunication, error detection and correction (EDAC) or error control are techniques that enable reliable delivery of digital data over unreliable communication channels. Many communication channels are subject to channel noise, and thus errors may be introduced during transmission from the source to a receiver. Error detection techniques allow detecting such errors, while error correction enables reconstruction of the original data in many cases.
The Graphics Interchange Format is a bitmap image format that was developed by a team at the online services provider CompuServe led by American computer scientist Steve Wilhite and released on June 15, 1987.
In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code is Huffman coding, an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".
In computer science and telecommunication, Hamming codes are a family of linear error-correcting codes. Hamming codes can detect one-bit and two-bit errors, or correct one-bit errors without detection of uncorrected errors. By contrast, the simple parity code cannot correct errors, and can detect only an odd number of bits in error. Hamming codes are perfect codes, that is, they achieve the highest possible rate for codes with their block length and minimum distance of three. Richard W. Hamming invented Hamming codes in 1950 as a way of automatically correcting errors introduced by punched card readers. In his original paper, Hamming elaborated his general idea, but specifically focused on the Hamming(7,4) code which adds three parity bits to four bits of data.
Reed–Solomon codes are a group of error-correcting codes that were introduced by Irving S. Reed and Gustave Solomon in 1960. They have many applications, the most prominent of which include consumer technologies such as MiniDiscs, CDs, DVDs, Blu-ray discs, QR codes, data transmission technologies such as DSL and WiMAX, broadcast systems such as satellite communications, DVB and ATSC, and storage systems such as RAID 6.
Range coding is an entropy coding method defined by G. Nigel N. Martin in a 1979 paper, which effectively rediscovered the FIFO arithmetic code first introduced by Richard Clark Pasco in 1976. Given a stream of symbols and their probabilities, a range coder produces a space-efficient stream of bits to represent these symbols and, given the stream and the probabilities, a range decoder reverses the process.
A prefix code is a type of code system distinguished by its possession of the "prefix property", which requires that there is no whole code word in the system that is a prefix of any other code word in the system. It is trivially true for fixed-length code, so only a point of consideration in variable-length code.
Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied by various scientific disciplines—such as information theory, electrical engineering, mathematics, linguistics, and computer science—for the purpose of designing efficient and reliable data transmission methods. This typically involves the removal of redundancy and the correction or detection of errors in the transmitted data.
In information theory, a low-density parity-check (LDPC) code is a linear error correcting code, a method of transmitting a message over a noisy transmission channel. An LDPC code is constructed using a sparse Tanner graph. LDPC codes are capacity-approaching codes, which means that practical constructions exist that allow the noise threshold to be set very close to the theoretical maximum for a symmetric memoryless channel. The noise threshold defines an upper bound for the channel noise, up to which the probability of lost information can be made as small as desired. Using iterative belief propagation techniques, LDPC codes can be decoded in time linear in their block length.
In telecommunications, 8b/10b is a line code that maps 8-bit words to 10-bit symbols to achieve DC balance and bounded disparity, and at the same time provide enough state changes to allow reasonable clock recovery. This means that the difference between the counts of ones and zeros in a string of at least 20 bits is no more than two, and that there are not more than five ones or zeros in a row. This helps to reduce the demand for the lower bandwidth limit of the channel necessary to transfer the signal.
PDF417 is a stacked linear barcode format used in a variety of applications such as transport, identification cards, and inventory management. "PDF" stands for Portable Data File. The "417" signifies that each pattern in the code consists of 4 bars and spaces in a pattern that is 17 units (modules) long. The PDF417 symbology was invented by Dr. Ynjiun P. Wang at Symbol Technologies in 1991. It is defined in ISO 15438.
In coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definition of block codes is conceptually useful because it allows coding theorists, mathematicians, and computer scientists to study the limitations of all block codes in a unified way. Such limitations often take the form of bounds that relate different parameters of the block code to each other, such as its rate and its ability to detect and correct errors.
Eight-to-fourteen modulation (EFM) is a data encoding technique – formally, a line code – used by compact discs (CD), laserdiscs (LD) and pre-Hi-MD MiniDiscs. EFMPlus is a related code, used in DVDs and Super Audio CDs (SACDs).
A Data Matrix is a two-dimensional code consisting of black and white "cells" or dots arranged in either a square or rectangular pattern, also known as a matrix. The information to be encoded can be text or numeric data. Usual data size is from a few bytes up to 1556 bytes. The length of the encoded data depends on the number of cells in the matrix. Error correction codes are often used to increase reliability: even if one or more cells are damaged so it is unreadable, the message can still be read. A Data Matrix symbol can store up to 2,335 alphanumeric characters.
In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels.
In computer science and information theory, a canonical Huffman code is a particular type of Huffman code with unique properties which allow it to be described in a very compact manner. Rather than storing the structure of the code tree explicitly, canonical Huffman codes are ordered in such a way that it suffices to only store the lengths of the codewords, which reduces the overhead of the codebook.
In coding theory, a variable-length code is a code which maps source symbols to a variable number of bits. The equivalent concept in computer science is bit string.
Consistent Overhead Byte Stuffing (COBS) is an algorithm for encoding data bytes that results in efficient, reliable, unambiguous packet framing regardless of packet content, thus making it easy for receiving applications to recover from malformed packets. It employs a particular byte value, typically zero, to serve as a packet delimiter. When zero is used as a delimiter, the algorithm replaces each zero data byte with a non-zero value so that no zero data bytes will appear in the packet and thus be misinterpreted as packet boundaries.
Sudoku codes are non-linear forward error correcting codes following rules of sudoku puzzles designed for an erasure channel. Based on this model, the transmitter sends a sequence of all symbols of a solved sudoku. The receiver either receives a symbol correctly or an erasure symbol to indicate that the symbol was not received. The decoder gets a matrix with missing entries and uses the constraints of sudoku puzzles to reconstruct a limited amount of erased symbols.
US 5591956,Longacre, Jr., Andrew&Hussey, Robert,"Two Dimensional Data Encoding Structure and Symbology for use with Optical Readers",published 1997-01-07
↑ Official Gazette. United States Patent Office. 17 June 1997. Hereby dedicates to the public the entire term of said patent. Click "images" then "correction" to see the dedication to the public domain.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
