A QR symbol this size contains 26 bytes of information. Some of these are used to store the message and some are used for error correction, as shown in the table below. The left-hand column is simply a name given to that level. The next three bits of format information select the masking pattern to be used in the data area. The patterns are illustrated below, including the mathematical formula that tells whether a module is black i and j are the row and column numbers, respectively, and start with 0 in the upper-left hand corner.
The remaining ten bits of formatting information are for correcting errors in the format itself. This will be explained in a later section. Here is a larger diagram showing the "unmasked" QR code. Different regions of the symbol are indicated, including the boundaries of the message data bytes. Data bits are read starting from the lower-right corner and moving up the two right-hand columns in a zig-zag pattern. The first three bytes are The next two columns are read in a downward direction, so the next byte is Upon reaching the bottom, the two columns after that are read upward.
Proceed in this up-and-down fashion all the way to the left side of the symbol skipping over the timing pattern where necessary. Here is the complete message in hexadecimal notation. The final step is to decode the message bytes into something readable.
The first four bits indicate how the message is encoded. QR codes use several different encoding schemes, so that different kinds of messages can be stored efficiently.
These are summarized in the table below. After the mode indicator is a length field, which tells how many characters are stored. The size of the length field depends on the specific encoding. Our sample message starts with hex 4 , indicating that there are 8 bits per character. The next 8 bits hex 0d are the length field, 13 in decimal notation. The whole message is "'Twas billig" from w:Jabberwocky Lexicon. After the last of the data bits is another 4-bit mode indicator.
It can be different from the first one, allowing different encodings to be mixed within the same QR symbol. When there is no more data to store, the special end-of-message code is given.
Note that the standard allows the end-of-message code to be omitted if it wouldn't fit in the available number of data bytes. At this point, we know how to decode, or read, a whole QR code. However, in real life conditions, a QR code is rarely whole: usually, it is scanned via a phone's camera, under potentially poor lighting conditions, or on a scratched surface where part of the QR code was ripped, or on a stained surface, etc.
The next part of this article will describe how to correct errors, by constructing a BCH decoder, and more specifically a Reed—Solomon decoder. In this section, we introduce a general class of error correction codes: the BCH codes , the parent family of modern Reed—Solomon codes, and the basic detection and correction mechanisms. The formatting information is encoded with a BCH code which allows a certain number of bit-errors to be detected and corrected.
In the case of QR codes, the BCH code used for the format information is much simpler than the Reed—Solomon code used for the message data, so it makes sense to start with the BCH code for format information. The process for checking the encoded information is similar to long division, but uses exclusive-or instead of subtraction. The format code should produce a remainder of zero when it is "divided" by the so-called generator of the code.
QR format codes use the generator This process is demonstrated for the format information in the example code below. Python note: The range function may not be clear to non-Python programmers. It produces a list of numbers counting down from 4 to 0. This is consistent with C-like languages. Readers may find it an interesting exercise to generalize this function to divide by different numbers.
For example, larger QR codes contain six bits of version information with 12 error correction bits using the generator In mathematical formalism, these binary numbers are described as polynomials whose coefficients are integers mod 2. Each bit of the number is a coefficient of one term.
For example:. The next step is to determine which format code is most likely the one that was intended ie, lookup in our reduced dictionary. Although sophisticated algorithms for decoding BCH codes exist, they are probably overkill in this case.
Since there are only 32 possible format codes, it's much easier to simply try each one and pick the one that has the smallest number of bits different from the code in question the number of different bits is known as the Hamming distance. This method of finding the closest code is known as exhaustive search, and is possible only because we have very few codes a code is a valid message, and here there are only 32, all other binary numbers aren't correct.
Note that Reed—Solomon is also based on this principle, but since the number of possible codewords is simply too big, we can't afford to do an exhaustive search, and that's why clever but complicated algorithms have been devised, such as Berlekamp-Massey. This happens when two or more format codes have the same distance from the input. The basic idea ie, using a limited words dictionary with maximum separability is the same, but since we will encode longer words bytes instead of 2 bytes , with more symbols available encoded on all 8bits, thus different possible values , we cannot use this naive, exhaustive approach, because it would take way too much time: we need to use cleverer algorithms, and Finite Field mathematics will help us do just that, by giving us a structure.
Before discussing the Reed—Solomon codes used for the message, it will be useful to introduce a bit more mathematics.
We'd like to define addition, subtraction, multiplication, and division for 8-bit bytes and always produce 8-bit bytes as a result, so as to avoid any overflow. Naively, we might attempt to use the normal definitions for these operations, and then mod by to keep results from overflowing.
Here's a brief introduction to Galois Fields: a finite field is a set of numbers, and a field needs to have six properties governing addition, subtraction, multiplication and division: Closure, Associative, Commutative, Distributive, Identity and Inverse. More simply put, using a field allows us to study the relationship between numbers of this field, and apply the result to any other field that follows the same properties. In other words, mathematical fields studies the structure of a set of numbers.
In spoken language, 2 is the characteristic of the field, 8 is the exponent, and is the field's cardinality.
More information on finite fields can be found here. The latter is often the representation used in academic books and in hardware implementations because of logical gates and registers, which work at the binary level. For a software implementation, the decimal representation can be preferred for clearer and more close-to-the-mathematics code this is what we will use for the code in this tutorial, except for some examples that will use the binary representation.
We will first describe operations on single symbol, then polynomial operations on a list of symbols. Both addition and subtraction are replaced with exclusive-or in Galois Field base 2. This is logical: addition modulo 2 is exactly like an XOR, and subtraction modulo 2 is exactly the same as addition modulo 2. This is possible because additions and subtractions in this Galois Field are carry-less.
Note that in books, you will find additions and subtractions to define some mathematical operations on GF integers, but in practice, you can just XOR as long as you are in a Galois Field base 2; this is not true in other fields. Multiplication is likewise based on polynomial multiplication. Simply write the inputs as polynomials and multiply them out using the distributive law as normal. As an example, times is calculated as follows.
The same result can be obtained by a modified version of the standard grade-school multiplication procedure, in which we replace addition with exclusive-or.
Note: the XOR multiplication here is carry-less! If you do it with-carry, you will get the wrong result with the extra term x 9 instead of the correct result These operators are available in most languages, they are not specific to Python, and you can get more information about them here. Of course, the result no longer fits in an 8-bit byte in this example, it is 13 bits long , so we need to perform one more step before we are finished. The result is reduced modulo the choice of this number is explained below the code , using the long division process described previously.
In this instance, this is called "modular reduction", because basically what we do is that we divide and keep only the remainder, using a modulo. This produces the final answer in our example. Why mod in hexadecimal: 0x11d? The mathematics is a little complicated here, but in short, represents an 8th degree polynomial which is "irreducible" meaning it can't be represented as the product of two smaller polynomials.
This number is called a primitive polynomial or irreducible polynomial, or prime polynomial we will mainly use this latter name for the rest of this tutorial. This is necessary for division to be well-behaved, which is to stay in the limits of the Galois Field, but without duplicating values. There are other numbers we could have chosen, but they're all essentially the same, and 0x11d is a common primitive polynomial for Reed—Solomon codes.
If you are curious to know how to generate those prime numbers, please see the appendix. Additional infos on the prime polynomial you can skip : What is a prime polynomial? It is the equivalent of a prime number, but in the Galois Field. Remember that a Galois Field uses values that are multiples of 2 as the generator. Of course, a prime number cannot be a multiple of two in standard arithmetics, but in a Galois Field it is possible. Why do we need a prime polynomial?
Because to stay in the bound of the field, we need to compute the modulo of any value above the Galois Field. Why don't we just modulo with the Galois Field size? Because we will end up with lots of duplicate values, and we want to have as many unique values as possible in the field, so that a number always has one and only projection when doing a modulo or a XOR with the prime polynomial.
Note for the interested reader: as an example of what you can achieve with clever algorithms, here is another way to achieve multiplication of GF numbers in a more concise and faster way, using the Russian Peasant Multiplication algorithm :.
The procedure described above is not the most convenient way to implement Galois field multiplication. Multiplying two numbers takes up to eight iterations of the multiplication loop, followed by up to eight iterations of the division loop. However, we can multiply with no looping by using lookup tables. One solution would be to construct the entire multiplication table in memory, but that would require a bulky 64k table.
The solution described below is much more compact. This is known as the discrete logarithm problem, and no efficient general solution is known. However, since there are only elements in this field, we can easily construct a table of logarithms. While we're at it, a corresponding table of antilogs exponentials will also be useful. More mathematical information about this trick can be found here.
A Reed-Solomon code is specified as RS n,k with s -bit symbols. This means that the encoder takes k data symbols of s bits each and adds parity symbols to make an n symbol codeword.
There are n-k parity symbols of s bits each. The following diagram shows a typical Reed-Solomon codeword this is known as a Systematic code because the data is left unchanged and the parity symbols are appended :. Each codeword contains code word bytes, of which bytes are data and 32 bytes are parity.
For this code:. The decoder can correct any 16 symbol errors in the code word: i. Reed-Solomon codes may be shortened by conceptually making a number of data symbols zero at the encoder, not transmitting them, and then re-inserting them at the decoder.
Example : The , code described above can be shortened to , The encoder takes a block of data bytes, conceptually adds 55 zero bytes, creates a , codeword and transmits only the data bytes and 32 parity bytes. The amount of processing "power" required to encode and decode Reed-Solomon codes is related to the number of parity symbols per codeword. A large value of t means that a large number of errors can be corrected but requires more computational power than a small value of t.
One symbol error occurs when 1 bit in a symbol is wrong or when all the bits in a symbol are wrong. Example : RS , can correct 16 symbol errors. In the worst case, 16 bit errors may occur, each in a separate symbol byte so that the decoder corrects 16 bit errors. In the best case, 16 complete byte errors occur so that the decoder corrects 16 x 8 bit errors. Reed-Solomon codes are particularly well suited to correcting burst errors where a series of bits in the codeword are received in error.
Reed-Solomon algebraic decoding procedures can correct errors and erasures. An erasure occurs when the position of an erred symbol is known. A decoder can correct up to t errors or up to 2t erasures. Erasure information can often be supplied by the demodulator in a digital communication system, i. The decoder will detect that it cannot recover the original code word and indicate this fact. The probability of each of the three possibilities depends on the particular Reed-Solomon code and on the number and distribution of errors.
If we corrupt one position more, Reed-Solomon is guaranteed to detect this, up to 8 corruptions in total:. However, Reed-Solomon can correct all 8 corruptions if we tell the decoder where they are:. As noted, as long as we are working with 8-bit symbols, the total codeword will always be bytes long. Depending on your needs, you might want more or less protection. Do note however that computer hardware will only rarely corrupt single bytes once they hit your programming language, that is.
It is far more common that an entire sector, disk or memory bank disappears on you. It is however very possible that your RAM corrupts single bits of data. Also, the TCP and Ethernet checksums are weak enough that corruptions can slip through undetected. This however is so rare that you are better off relying on cryptography to detect such data integrity problems and retransmit entirely.
R-S is not worth it in this domain. With the perhaps notable exception of ZFS which on its initial introduction found heaps of corruptions happening in servers and drives. A much more common problem for programmers is the outright disappearance of data.
This happens all the time - disks fail frequently, even SSDs, perhaps more so even. In addition, networks drop packets all the time. Note that we must also add a sequence number to each packet. This allows the receiver to detect exactly which packets are missing. If nothing gets lost, the receiver waits until all 5 packets are in, and undoes the smearing out. Running the Reed-Solomon decoder will in this case only detect any very rare individual corrupted bytes.
To recover from that, the R-S decoder needs to know exactly which parts of the message got lost. And luckily we know this because we know the distribution schema and we know which packet got lost. Thus informed, R-S is able to reconstruct the four original packets perfect, and our audio stream is not interrupted. The above is a very simple example of how to use R-S to gain resilience against serious amounts of data loss. Do note however that it pays to put a lot of thought in such schemes.
What will the packet loss look like? Might it come in bursts? And what kind of latency is acceptable? A very efficient setup might well buffer 30 seconds of data, which is useless for live interviews for example. The scheme outlined above also works for redundant file and data storage. This turns a , code into , R-S continues to work just as well, even if you know none of your padding will ever get corrupted.
It is tempting to be clever about this and transmit a length field so you can do dynamically sized code word. Otherwise a corruption in the length field might knock you out.
0コメント