QRDecoders
QR Codes decoder with support of Numeric
mode, Alphanumeric
mode, Kanj
mode, Byte
mode and UTF8
mode.
The decoding rules of QRDecoders.jl are compatible with QRCoders.jl.
Decoding message from QR codes
QRDecoders.QRInfo
— TypeQRInfo
A struct to store the information of a QR code.
Fields
version::Int
: version of the QR codeeclevel::Int
: error correction level of the QR codemask::Int
: mask of the QR codemode::Int
: mode of the QR codemessage::String
: decoded message
QRDecoders.qrdecode
— Functionqrdecode(mat::AbstractMatrix
; noerror::Bool=false
, preferutf8::Bool=true
, alg::ReedSolomonAlgorithm=Euclidean()
)::QRInfo
QR code decoder.
If noerror
is true
, the decoder will raise an Exception(ReedSolomonError/InfoError) when the QR code mat
needs error correction.
If preferutf8
is true
, the decoder will try to decode the message by UTF8
mode when dealing with Byte
mode.
The error correction algorithm is specified by the variable alg
(default: Euclidean
).
qrdecode(path::AbstractString; keywords...)
QR code decoder.
For more information of the keywords, see qrdecode(mat::AbstractMatrix; keywords...)
.
QRDecoders.qrdecompose
— Functionqrdecompose(mat::AbstractMatrix, noerror=false)
Decompose the QR-Code into its constituent parts.
QRDecoders.getqrmatrix
— Functiongetqrmatrix(img)
Get the QR-code matrix from an image.
Note that the input must be a standard QR-code image with or without white border, i.e. the image should not contain any other non-QR-Code information.
Decoding procedures
Check the version and format information
QRDecoders.qrdecode_version
— Functionqrdecode_version(version::Int)
Decode version information.(Interger to Integer)
qrdecode_version(mat::AbstractMatrix; noerror=false)
Return the version of the QR-Code.(Matrix to Integer)
QRDecoders.qrdecode_format
— Functionqrdecode_format(fmt::Int)::Int
Decode format information.
qrdecode_format(mat::AbstractMatrix; noerror=false)
Return the format of the QR-Code(ErrCorrLevel + mask).
Extract message bits
QRDecoders.extract_databits
— Functionextract_databits(mat::AbstractMatrix, datapos::AbstractMatrix)
Extract data bits from the QR-Code.(Inverse procedure of placedata!)
QRDecoders.deinterleave
— Functiondeinterleave(bytes::AbstractVector, ec::ErrCorrLevel, version::Int)
De-interleave the message, i.e. sperate msgblocks and ecblocks from data bits.
QRDecoders.block2bits
— Functionblock2bits(blocks::AbstractVector)
Convert a block to bits.
Error correction
QRDecoders.correct_message
— Functioncorrect_message(msgblock::AbstractVector
, ecblock::AbstractVector
, alg::ReedSolomonAlgorithm
; noerror::Bool=false)
Error correction of the message block using the given algorithm.
Throw DecodeError if the value noerror
is true and the message need error correction.
Decode message
QRDecoders.decodemode
— Functiondecodemode(bits::AbstractVector)
Decode mode from the bits of length 4. Note: the Byte
mode and the UTF8
mode use the same mode indicator(0100).
QRDecoders.decodedata
— Functiondecodedata(bits::AbstractVector, msglen::Int, ::Mode)
Decode message from bits
without checking the pad_bits
.
Syndrome Decoding
Algorithm for decoding error correction codes.
QRDecoders.ReedSolomonAlgorithm
— TypeReedSolomonAlgorithm
An abstract type for error correction algorithm of Reed Solomon code.
QRDecoders.Euclidean
— TypeEuclidean <: ReedSolomonAlgorithm
Euclidean algorithm for error correction.
QRDecoders.BerlekampMassey
— TypeBerlekampMassey <: ReedSolomonAlgorithm
Berlekamp-Massey algorithm for error correction.
QRDecoders.Syndrome.RSdecoder
— FunctionRSdecoder(received::Poly, nsym::Int, ::ReedSolomonAlgorithm)
Decode the message polynomial using the given Reed-Solomon algorithm.
QRDecoders.Syndrome.berlekamp_massey_decoder
— Functionberlekamp_massey_decoder(received::Poly, erasures::AbstractVector, nsym::Int)
Berlekamp-Massey algorithm, decode message polynomial from received polynomial(given erasures).
berlekamp_massey_decoder(received::Poly, nsym::Int)
Berlekamp-Massey algorithm, decode message polynomial from received polynomial(without erasures).
QRDecoders.Syndrome.euclidean_decoder
— Functioneuclidean_decoder(received::Poly, erasures::AbstractVector, nsym::Int)
Decode the received polynomial using the Euclidean algorithm(with erasures).
euclidean_decoder(received::Poly, erasures::AbstractVector, nsym::Int)
Decode the received polynomial using the Euclidean algorithm(without erasures).
Tools for Syndrome Decoding.
QRDecoders.Syndrome.syndrome_polynomial
— Functionsyndrome_polynomial(received::Poly, nsym::Integer)
Computes the syndrome polynomial S(x) for the received polynomial where nsym
is the number of syndromes.
QRDecoders.Syndrome.evaluator_polynomial
— Functionevaluator_polynomial(sydpoly::Poly, errlocpoly::Poly, nsym::Int)
Return the evaluator polynomial Ω(x) where Ω(x)≡S(x)Λ(x) mod xⁿ.
QRDecoders.Syndrome.erratalocator_polynomial
— Functionerratalocator_polynomial(errpos::AbstractVector)
Compute the erasures/error locator polynomial Λ(x) from the erasures/errors positions.
erratalocator_polynomial(sydpoly::Poly, nsym::Int; check=false)
Compute the error locator polynomial Λ(x)(without erasures). The check
tag ensures that Λx can be decomposed into products of one degree polynomials.
erratalocator_polynomial(sydpoly::Poly, erasures::AbstractVector, n::Int)
Berlekamp-Massey algorithm, compute the error locator polynomial Λ(x)(given the erased positions). The check
tag ensures that Λx can be decomposed into products of one degree polynomials.
QRDecoders.Syndrome.haserrors
— Functionhaserrors(received::Poly, nsym::Int)
Returns true if the received polynomial has errors. (may go undetected when the number of errors exceeds n)
QRDecoders.Syndrome.fillerasures
— Functionfillerasures(received::Poly, errpos::AbstractVector, nsym::Int)
Forney algorithm, computes the values (error magnitude) to correct the input message.
Warnning: The output polynomial might be incorrect if errpos
is incomplete.
QRDecoders.Syndrome.Sugiyama_euclidean_divide
— FunctionSugiyama_euclidean_divide(r₁::Poly, r₂::Poly, upperdeg::Int)
Yasuo Sugiyama's adaptation of the Extended Euclidean algorithm. Find u(x), v(x) and r(x) s.t. r(x) = u(x)r₁(x) + v(x)r₂(x) where r(x) = gcd(r₁(x), r₂(x)) or deg(r(x)) ≤ upperdeg.
Tools for polynomials.
QRDecoders.Syndrome.polynomial_eval
— Functionpolynomial_eval(p::Poly, x::Integer)
Evaluates the polynomial p(x) at x in GF256.
QRDecoders.Syndrome.derivative_polynomial
— Functionderivative_polynomial(p::Poly)
Computes the derivative of the polynomial p.
QRDecoders.Syndrome.findroots
— Functionfindroots(p::Poly)
Computes the roots of the polynomial p using Horner's method.
The output will be an empty list if p(x) contains duplicate roots or roots not in GF(256).
QRDecoders.Syndrome.reducebyHorner
— FunctionreducebyHorner(p::Poly, a::Int)
Horner's rule, find the polynomial q(x) such that p(x)-(x-a)q(x) is a constant polynomial.
QRDecoders.Syndrome.getpositions
— Functiongetpositions(Λx::Poly)
Caculate positions of errors from the error locator polynomial Λx. Note that the indexs start from 0.
QRDecoders.Syndrome.extended_euclidean_divide
— Functionextended_euclidean_divide(r₁::Poly, r₂::Poly)
Return polynomials u(x) and v(x) such that u(x)r₁(x) + v(x)r₂(x) = gcd(r₁(x), r₂(x)).
illustration
Let
\[r_k = u_kr_1 + v_kr_2,\quad k \geq 2\]
Then
\[\begin{aligned} r_0 &= q_0r_1 + r_2 \quad\Rightarrow r_2 = r_0 - q_0r_1,\ where\ r_0=r_2,\ q_0=0\\ r_1 &= q_1r_2 + r_3 \quad\Rightarrow r_3 = r_1 - q_1r_2\\ r_2 &= q_2r_3 + r_4 \quad\Rightarrow r_4 = r_2 - q_2r_3\\ &\vdots\\ r_k &= q_kr_{k+1} + r_{k+2}\Rightarrow r_{k+2} = r_k - q_kr_{k+1}\\ &\phantom{= q_kr_{k+1} + r_{k+2}\Rightarrow r_{k+2}} = u_kr_1 + v_kr_2 - q_k(u_{k+1}r_1 + v_{k+1}r_2)\\ &\phantom{= q_kr_{k+1} + r_{k+2}\Rightarrow r_{k+2}} = (u_k - q_ku_{k+1})r_1 + (v_k - q_kv_{k+1})r_2 \end{aligned}\]
Loop until $r_t = q_tr_{t+1} + 0$, then $r_{t+1}$ is the greatest common factor of $r_1$ and $r_2$.
Here we obtain the recursive formula of $u_k$ and $v_k$. ```math \begin{aligned} u2, v2 &= 0, 1,\quad u3, v3 = 1, -q1\ u{k+1} &= uk - qku{k+1},\quad v{k+1} = vk - qkv_{k+1} \end{aligned}
Error types
QRDecoders.InfoError
— TypeInfoError <: Exception
The non-data part of QR-matrix contains error.
For example, Finder pattern, Alignment pattern, Timing pattern, Format information, Version information, matrix size and etc.
QRDecoders.DecodeError
— TypeDecodeError <: Exception
The data part of QR-matrix contains error.
QRDecoders.ReedSolomonError
— TypeReedSolomonError <: Exception
An error occurs during error-correction.