CN102004935A

CN102004935A - LDPC (Low Density Parity Code)-based method for encoding and decoding two dimensional bar codes

Info

Publication number: CN102004935A
Application number: CN 201010534320
Authority: CN
Inventors: 佟野
Original assignee: Individual
Current assignee: Individual
Priority date: 2010-11-08
Filing date: 2010-11-08
Publication date: 2011-04-06

Abstract

The invention relates to an LDPC (Low Density Parity Code)-based method for encoding and decoding two dimensional bar codes, comprising the following steps of: obtaining input information according to encoding type process of the input binary data information; carrying out lengthening compression or fixed-length compression on the input information; calculating an information length required for storing according to a compressed result, obtaining the information to be encoded according to the encoding type and the compression type; carrying out LDPC encoding compression on the information to be encoded; integrating the compressed result and the version information to obtain the compressed information; and setting a flag bit and generating a two dimensional bar code image. The encoding method has large information capacity and strong error correction capability; the aspect ratio can be optionally set; and various types of encoding are supported and the locating is easier.

Description

Two-dimensional bar code coding and decoding method based on LDPC code

Technical Field

The invention relates to a method for coding and decoding a two-dimensional bar code, in particular to a method for coding and decoding a two-dimensional bar code based on an LDPC code.

Background

The bar code technology has been developed rapidly since the beginning of the 70 s in the 20 th century, and is only 20 years old, and is widely applied to the fields of commercial circulation, storage, medical and health, book information, post, railway, transportation, production automation management and the like. The application of the bar code technology greatly improves the speed of data acquisition and information processing, improves the working and living environments of people, improves the working efficiency and makes important contribution to the scientification and modernization of management.

The early development of the bar code technology adopts a one-dimensional bar code, information is expressed by horizontally arranged bars and spaces, the data volume is small, only letters and numbers can be stored, the size is large, and the bar code cannot be read after being damaged. In the application system of the universal commodity bar code, description of commodity information such as production date, price and the like must depend on the support of a database. In places where a commodity database is not established in advance or where networking is inconvenient, it is almost impossible for a one-dimensional bar code to represent Chinese characters and image information, and even if the Chinese characters and the image information can be represented, the Chinese characters and the image information are inconvenient and have low efficiency.

The two-dimensional bar code has the characteristics of large storage capacity, high confidentiality, high traceability, strong damage resistance, high redundancy, low cost and the like, and the characteristics are particularly suitable for the aspects of forms, security, confidentiality, tracking, license, stock counting, data redundancy and the like.

Among the present dozens of two-dimensional codes, the common code systems are: PDF417 two-dimensional barcode, Datamatrix two-dimensional barcode, Maxicode two-dimensional barcode, QR Code, Code49, Code 16K, Code one, and the like, and in addition to these common two-dimensional barcodes, Vericode barcode, CP barcode, Codablock F barcode, field Code, Ultracode barcode, Aztec barcode. These two-dimensional barcodes can be divided into two categories: a stack type/row type two-dimensional bar code and a matrix type two-dimensional bar code.

The stacked/row-type two-dimensional bar code is formed by stacking a plurality of rows of short one-dimensional bar codes, inherits some characteristics of the one-dimensional bar code in aspects of coding design, verification principle, reading mode and the like, and the reading equipment is compatible with bar code printing and one-dimensional bar code technology. However, due to the increase of the number of rows, the rows need to be determined, and the decoding algorithm and software thereof are not exactly the same as the one-dimensional bar code. Representative row-by-row two-dimensional barcodes are CODE49, CODE 16K, PDF417, and the like. PDF417 (US 5304786A) is composed of a plurality of control patterns of one-dimensional bar codes, and has the defect that a coding mode based on 929 code words (4 black and white intervals) is adopted, each bar code character can only represent 9.2 bit data, and the data volume of a single PDF417 bar code is greatly reduced.

The matrix type two-dimensional bar code is also called as a chessboard type two-dimensional bar code and is composed of a matrix, wherein a binary system 1 is represented by a dot on the corresponding element position of the matrix, a binary system 0 is represented by a null, and codes are formed by the arrangement of the dot and the null. Representative matrix two-dimensional barcodes are: code One, Maxi Code, QR Code, Data Matrix, etc. QR Code is a matrix two-dimensional Code developed by Denso corporation of Japan in 9 months of 1994 and used for industrial automation, and a bar Code can only be square and cannot be scanned and synchronously decoded. Although QR Code can represent Chinese characters, the number of representations is limited. The capacity is also limited and theoretically can only represent 1817 "kanji" characters. The maximum data capacity is 2956 bytes when 750 error correction bytes are the lowest of 177Z-sizes in its maximum area and the error correction capability. QR Code, Data Matrix and the like tend to be squares which are simple and easy to read compared with the design of a general two-dimensional Code, and the corresponding layout needs to be redesigned in the process of replacing the one-dimensional Code.

When the two-dimensional codes are used for printed products, the images of the two-dimensional codes are blurred due to the fact that the printed products are prone to abrasion, the recognition rate is reduced, and the two-dimensional codes on the market at present have no good solution.

LDPC codes, that is, Low Density Parity Check codes (LDPC), which are linear block codes with sparse Check matrices proposed by Robert g.gallager in 1963, a class of linear codes defined by Check matrices needs to satisfy "sparsity" when the Code length is longer, that is, the Density of 1 in a Check matrix is lower, that is, the number of 1 in a Check matrix is far less than 0, and the longer the Code length, the lower the Density is. The LDPC has good performance approaching to Shannon limit, low decoding complexity and flexible structure, is a research hotspot in the field of channel coding in recent years, and is widely applied to the fields of deep space communication, optical fiber communication, satellite digital video, audio broadcasting and the like. LDPC codes have become a powerful competitor to fourth generation communication systems (4G), and LDPC code-based coding schemes have been adopted by the next generation satellite digital video broadcasting standard DVB-S2. The most recent IEEE 802.16E lists the recommended coding method.

With the development of modern high and new technology, bar codes are urgently needed to represent more information in a limited geometric space so as to meet the requirement of ever-changing information representation. Particularly, a two-dimensional bar code with large information capacity and strong error correction capability is needed, the length-width ratio can be set optionally, various types of codes can be supported, and the positioning is easier.

Disclosure of Invention

For the above reasons, the present invention is intended to provide a two-dimensional barcode with large information capacity and strong error correction capability, which preferably can arbitrarily set the length-width ratio, support multiple types of codes, and facilitate positioning.

Therefore, the invention provides a coding method of a two-dimensional bar code based on LPDC coding, which is used for outputting the two-dimensional bar code which can be attached on a carrier by the input original binary data information through a coding compression method based on low density parity check code (LDPC), and is characterized by comprising the following steps:

A. processing according to the coding type of the input original binary data information to obtain byte type input information;

B. performing first compression on the input information of the byte type, wherein the compression type of the first compression can be variable length compression or fixed length compression;

C. calculating the length of information to be stored according to the first compression result, and obtaining information to be encoded according to the encoding type and the compression type;

D. performing second compression on the information to be coded, wherein the second compression is LDPC coding compression;

E. integrating the second compression result with the version information to obtain compressed information;

F. setting a flag bit and generating a two-dimensional bar code image.

In addition, the invention also correspondingly provides a decoding method of the two-dimensional bar code based on the LPDC code. The method uses a one-dimensional linear array contact type or non-contact type image sensor to obtain image data of a two-dimensional bar code, and recovers and outputs binary data information by a decoding method based on LDPC, and is characterized by comprising the following steps:

A. ashing the two-dimensional bar code image data by adopting a mean ashing method to obtain a gray value corresponding to each code element;

B. searching a positioning identifier according to the mark bitmap sample and acquiring a pixel size value;

C. reading effective information obtained by ashing in a blocking mode according to the pixel size value;

D. optimizing the effective information by adopting a binomial distribution method;

E. intercepting version information from the effective information;

F. performing first decoding on the remaining part of the valid information after the version information is truncated, wherein the first decoding can be LDPC decoding;

G. intercepting header information containing an encoding type and a compression type from a result obtained by the first decoding;

H. performing second decoding on the result obtained by the first decoding according to the header information;

I. binary data information is generated according to a result of the second decoding.

The invention effectively combines the two-dimension code and the LDPC code, simultaneously makes better correction aiming at the limitation of the existing two-dimension code, reformulates a set of method for generating and analyzing the two-dimension code, and has the following advantages:

1. the LDPC code is adopted to replace the Reed-Solomon error correcting code, so that higher code rate is obtained and the coding capacity is increased at the same code length. When decoding, image information is output in a soft mode, and a Belief Propagation (BP) decoding mode is adopted, so that a blurred image is easier to identify, and the two-dimensional code has stronger error correction performance. And calculating the code element 01 probability according to the binomial distribution characteristics, and increasing the decoding performance of the fuzzy two-dimensional code.

2. The length-width ratio can be set arbitrarily, so that the existing rectangular one-dimensional code can be replaced conveniently.

3. GB18030 and UTF-8 types are supported by default, and other customized types of codes are supported.

4. And two compression modes of fixed length and Huffman variable length are adopted, so that the compression ratio of the information is improved, and the information capacity is further increased.

5. The ultra-large coding space can theoretically support 65535 byte information quantity, and a simulation test can easily compile and solve 20000 Chinese characters.

6. The two-dimensional code locator pattern which is complex and has poor practicability is cancelled, and the simple and effective locating pattern is used, so that the locating is easier.

Drawings

The flow of the encoding and decoding method of the two-dimensional barcode based on the LPDC encoding according to the present invention will be described in detail with reference to the accompanying drawings.

FIG. 1 is a flow chart of a method of encoding a two-dimensional barcode based on LPDC encoding;

FIG. 2 is a flow chart of a method of LPDC encoding used in the present invention;

FIG. 3 is a flow chart of a method of decoding a two-dimensional barcode based on LPDC encoding;

FIG. 4 is a flow chart of a method of LPDC decoding used in the present invention;

FIGS. 5a and 5b are schematic diagrams of the construction of a junction using Huffman compression according to the present invention;

FIG. 5c is a schematic diagram of the bit structure used in the present invention;

FIG. 6 is a schematic diagram of a flag bit of a two-dimensional barcode according to the present invention; and

fig. 7 is a schematic diagram of a binomial distribution log-likelihood ratio function according to the present invention.

Detailed Description

The features and technical effects of the technical scheme of the invention are explained in detail with reference to the attached drawings, and a two-dimensional bar code encoding and decoding method based on LDPC codes is disclosed.

Fig. 1 shows a basic flow of a two-dimensional barcode encoding method based on LDPC codes according to the present invention.

Step 100, inputting characters to be processed. The characters entered may be numbers, letters, ASCII code, ISO-8859-1 character set, GB18030 character set, UTF8 character set, etc. Compared with the QR code coding method commonly used by the current two-dimensional bar code, the invention increases the coding type of GB18030, supports all Chinese characters by default, can only support more than 6000 Chinese characters in the KANJI type in the QR code, and is not limited by Chinese character coding in application.

Step 101, an input array is obtained according to input characters. The input array is a byte array, and the following 6 coding types are supported by default. Each type has an identifier v for identifying the character set, a fixed value defined for the encoding method. The number of bits required for each character is represented by a block value, which is used for subsequent determination of the type of compression. The 6 coding types are respectively:

a) numeric digital type

The identification value is v ═ 1. The characters include [ 0123456789, -/: the required bit number block is 4. Wherein,

0-9 represent numbers

10 space (corresponding to ASCII code 32)

11 represents comma "," (corresponding to ASCII code 44)

12 represents a dash "-" (corresponding to an ASCII code of 45)

13 represents a period ". The" ("46" for ASCII code)

14 represents slash "/" (corresponding to ASCII code 47)

15 represents a colon ": "(corresponding ASCII code is 58)

b) Alpha letter type

The identification value is v-2. The characters include | -) and ASCII codes from 32 to 94, and the required bit number block is 6. When selecting this letter type, it is necessary to convert all the lower case letters in the incoming character string into upper case letters.

0-61 represents ASCII code 32-94

62 represents a vertical bar "|", (corresponding to the ASCII code of 124)

63 represents the wave number "-" (126 for ASCII code)

c) ASCII code type

The identification value is v-3. The character comprises 128 ASCII codes, and the required bit number block is 7.

d) Byte type

The identification value is v-4. The ISO-8859-1 character set is used by default, and the required bit number block is 8. When the Byte type is adopted, the Byte array can be directly transmitted for coding, and the Byte array is returned after decoding without transcoding.

e) CN type

The identification value is v-5. The block of the number of bits needed by the Chinese character is 8. And transcoding by using a GB18030 character set, and not performing other processing on the byte array.

f) UTF8 type

The identification value is v-6. The required bit number block is 8. And the UTF8 character set is adopted for transcoding, and other processing is not carried out on the byte array.

The length of the byte array obtained in step 101 is defined as n.

And 102, performing Huffman compression on the input array obtained in the step 101, namely the byte array. The Huffman compression in step 102 is a variable length compression mode, and the occurrence frequency of each byte in the first byte array is firstly counted to construct a Huffman tree, wherein the right child node is 0, and the left child node is 1.

And after the word frequency is counted, storing the Huffman tree by adopting a post-order traversal and node degree adding algorithm. And (3) setting each node to have a state bit of 0-3, wherein 0 represents that the node is a leaf node, 1 represents that the node only has a left sub-node, 2 represents that the node only has a right sub-node, and 3 represents that the node has a left sub-node and a right sub-node, and the state bit is the node degree of each node. And traversing the Huffman tree in a subsequent order, and simultaneously calculating the node degree of each node. Each node may be stored as 8-bit node information + 2-bit node degrees.

During decoding, only leaf nodes in the Huffman tree are used, so that a 1-bit flag is added before each node information, as shown in fig. 5 a. When the identification bit is 1, the node is valid, and 8 bits of node information follow. When the node information is 0, the node information is useless, the node information is not stored at the back, and 2-bit node degrees are followed.

In order to improve the compression ratio, the number of bits, i.e., the block value, of the node information storage may be determined according to the encoding type v. As shown in fig. 5b, for example, when the Alpha type is used, block is 6, and each node information requires only 6 bits.

After a series of compression, the bit of the Huffman tree is cp, that is, the Huffman tree obtained after the compression has the length of cp, and the corresponding variable length information has the length of p. The results of the compression are saved.

Step 103, judging the compression type. The compression type is identified by ctype, when the length n of the input byte array meets n × block > cp + p, Huffman compression is adopted, the ctype is set to be 1, the Huffman compression result obtained in the step 102 is not adjusted, and the Huffman compression tree is directly called during subsequent processing. Otherwise, that is, when the byte array length n satisfies n × block ≦ cp + p, fixed-length compression should be adopted, set ctype ≦ 0, discard Huffman compression, and re-compress again by fixed-length compression.

The Huffman coding adopted in step 102 has a higher compression ratio than the fixed-length addition method of QRcode, and the Huffman tree can be compressed according to the set coding type.

And 104, calculating the length of the stored information. Assuming that the number of information bits is k and the code length is N, the code rate R is k/N, (where k is equal to the sum of the number of header information bits and the number of compressed information bits), and N is k/R. In the later encoding process, we use the QC-LDPC code in IEEE 802.16e, which requires that the code length must be an integer multiple of 24, so we find the minimum N that meets the condition from R and k, and then find the minimum N × R, L ═ k, where the information length L is the minimum.

In the fixed-length compression, k is 4+3+16+ number of compression information bits.

In Huffman compression, k is 4+3+12+16+ Huffman tree information length cp + variable length information length p.

The spreading factor z is defined as L/24.

Step 105, header information is set. And defining an array to be coded, namely bit array data with the initial length of L, and storing the data to be coded. The first 4 bits of the data store a coding type value v, and the next 3 bits store a compression type value ctype. v and ctype jointly form the header information of the array data to be encoded.

Step 106, setting the compression information. When the fixed-length compression is carried out, 16-bit length is added in the data of the array to be encoded, so as to store the length n of the input array-byte array. And then adding the bytes in a circulating manner, wherein each byte occupies block bits. When Huffman compression is carried out, 12 bits are added in the data, and the number of nodes of the Huffman tree is stored; adding 16 bits and storing the byte array length n; adding Huffman tree information with the length of cp; after which compressed variable length information of length p is added. As follows:

after the compressed information is added, if the added length is smaller than the information length L in step 104, the remaining bits are randomly added. The random rule is: 1/3 has a probability of 1 and 2/3 has a probability of 0.

And step 107, performing LDPC coding on the array data to be coded. In order to improve efficiency, the data to be encoded is segmented and encoded according to a longest sLen of 2304 × R. Referring to fig. 2, the data array to be encoded is segmented and encoded by using a standard LDPC algorithm commonly used in the art. The specific algorithm can refer to IEEE 802.16e Annex G: LDPC direct encoding, G.6Method 2.

For example, firstly setting a code length (the length of each segment after segmentation) and a code rate R, obtaining a specified template matrix Hbm according to the code rate R, then generating a base matrix Hb, and dividing the Hb into the following forms according to a myopia lower triangular matrix coding method:

wherein m is_bIs a data bit of the base matrix, n_bIs the code length of the basis matrix, k_b＝n_b-m_b. Let the input codeword be u, the brief calculation procedure is as follows:

1) calculating Au^TAnd Cu^T

2) Calculating ET^-1(Au^T)

3) Calculating p₁ ^T＝ET^-1(Au^T)+Cu^T

4) Calculating p₂ ^T，Tp₂ ^T＝Au^T+Bp₁ ^T

The output code word c ═ u p is obtained through the calculation₁ p₂]And c is output data after each segment of coding is successful. And sequentially splicing the outputs of all the segments into a large array LData, wherein the total length is LLEn, LLEn is L/R, and L is the length L of the array data to be coded. In the encoding process, 4 error correction Level levels can be adopted, and the corresponding code rates R are respectively as follows:

a) height of

The code rate R is 1/2 and the Level is 3. Corresponding to the 1/2 code rate in IEEE 802.16 e.

b) In

The code rate R is 2/3 and the Level is 2. Corresponding to the 2/3a code rate in IEEE 802.16 e.

c) In general

The code rate R is 3/4 and the Level is 1. Corresponding to the 3/4a code rate in IEEE 802.16 e.

d) Is low in

The code rate R is 5/6 and the Level is 0. Corresponding to the 5/6 code rate in IEEE 802.16 e.

Step 108, the total number of symbols is calculated. Fig. 6 is a diagram of a flag bit, where 8 × 8 cells are occupied by the upper left, upper right, and lower left of a two-dimensional barcode image, where 7 × 7 cells near the border represent 1 in black, the area indicated by a circle of dotted lines around the border represents 0, one cell at the lower right of the image represents 1 in black, and the rest is valid information of a non-flag bit. Therefore, the number of symbols occupied by the flag bit is: 8 × 8 × 3+1 is 193. The aspect ratio of the generated image is defined as ratio, which can be input from the outside, and the value thereof is at least 1.

The version information of the two-dimensional bar code is fixed to be 48. The total length of the valid information is sum + LLen +193+ 48. Assuming that the width y and the length x of the finally generated two-dimensional barcode image are y × ratio, the root of y is (sum/ratio) is derived from x × y > -sum, that is, (y × ratio) × y > -sum, and y should be greater than or equal to (2 × 8+1), so that enough space is ensured for displaying the marker bit. From the minimum y derived above, x is y × ratio, where x should be an integer. And finally obtaining the total number of the code elements, namely x multiplied by y.

Step 109, generating version information. The version information has a fixed length of 48, consists of 24 bit information bits and 24 bit check bits, and is coded by an LDPC code with a code rate of 1/2. As shown in fig. 5c, is a composition of 24 bits of information therein.

The version number is started from 1, and can be upgraded by later expansion, and at most 32 versions can be provided. The next 17 bits store the value after LLEn/24. And finally storing the code rate Level by 2 bits. The 24-bit information bit is subjected to LDPC coding to obtain an information check bit array VData.

Step 110, integrate the arrays. And generating a code integration array TData with the length of (total-193) for storing other information except the flag bit. First, 48 bits of version information are added at 1/2 of the array, then the LDPC coded array LData after LDPC coding is added from the head, and the second half is filled in order from the 48 bits of version information after the first half is filled. The processing advantages are as follows: 1) an image is easier to generate, only mark positions are added at 4 corners in the image generation stage, a complex path-finding algorithm is not needed, and the method is quicker and simpler; 2) the analysis is easier, after the image is analyzed, the flag bit is conveniently removed, the version information is easily obtained from 1/2, and the position of the version information does not need to be separately identified like the QRCODE; 3) because the total length is not fixed, the version information has certain randomness in position and is not easy to be damaged maliciously. After the LDPC coding array LData is filled, the rest bits in the coding integration array TData are added randomly. The random rule is: 1/3 has a probability of 1 and 2/3 has a probability of 0.

And step 111, setting a flag bit. And generating a two-dimensional image array bid with dimensions x and y respectively. The two-dimensional array is regarded as a matrix, the size ranges of 7 multiplied by 7 at the upper left, the upper right and the lower left of the matrix are set to be 1, and a circle of 0 is added on the periphery of the 7 multiplied by 7. The lower right corner is then set to 1. This sets the flag bit shown in step 108. The marker bit is a fixed four corner, and although the marker bit has the characteristic of being recognizable by rotating 360 degrees like QRCODE, the marker bit is faster to recognize because of simple pattern.

And step 112, generating a two-dimensional bar code image. The information of the code integration array TData is added to the two-dimensional image array bid line by line in the order from left to right. Each piece of information is a small square, the length and the width of each square are scale pixels, and the size of each pixel can be defined by initial input. 1 and 0 are distinguished by different two colors.

The two-dimensional barcode encoding method based on LDPC encoding according to the present invention is described above with reference to fig. 1.

A decoding method of an LDPC coded-based two-dimensional barcode according to the present invention will now be described with reference to fig. 3.

Step 201, scanning an image. Ashing all elements in the two-dimensional bar code image to be decoded by using a mean ashing method, and storing the obtained result in an ashing result array in the form of an integral value with the gray value between 0 and 255. The invention is different from the existing two-dimensional code decoding technology, the special gray value during image analysis is utilized during decoding, the data of each pixel which has only 0 and 1 values is soft output to be in the form of 0-255 gray values, the image information is fully utilized, and then the decoding is carried out by a Belief Propagation (BP) algorithm, so that the fuzzy image is easier to identify, and the two-dimensional code has stronger error correction.

Step 202, finding a positioning identifier. And searching a positioning identifier according to the mark bitmap sample, judging whether the image needs to be turned over according to the found positioning identifier, and turning over the image if the positioning identifier of the two-dimensional bar code is inconsistent with a preset value. And obtains the scale value, i.e., the width of the pixel block occupied by each symbol. The specific process of positioning may apply techniques known in the art, for example as described in CN 1818926.

Step 203, soft output information bits. And reading the information in blocks according to the scale size, and then removing the identification bits to obtain an effective information array sout, wherein each value in the effective information array is the gray value of the corresponding information.

And step 204, optimizing the effective information array sout by adopting two-term distribution. LLR values are calculated firstly, the LLR values are log-likelihood ratios of binomial distribution, and the ratio values are related to LDPC decoding and are propagated when belief propagation decoding is adopted. Since the information bit is not 0, i.e., 1, the probability of "0 | 1" is taken to conform to a binomial distribution, with a maximum probability of 0.98 and a minimum probability of 0.02. The two-term distribution has the formula f (x) 0.98e ^ (x-255) ^2/(2 x 91^2)), and x is the gray scale value of the information bit. The distribution is shown in figure 7 below.

Let log-likelihood ratio l (x) be ln (p (x) 0)/p (x) 1), and p (x) be 0, which represents the probability that x is 0, i.e., LLR. Because there are only 256 gray values, the LLR values can be found by a table lookup. And traversing the effective information array sout after the LLR is obtained, and covering the original value by using the LLR value corresponding to each gray value in the array obtained by calculation. In this way, the probability of the code element 01 is calculated according to the binomial distribution characteristics, and the decoding performance of the fuzzy two-dimensional code can be improved.

In step 205, version information is intercepted. At 1/2 of the valid information array of the soft output, 48 bits are truncated as version information. Setting code rate 1/2 and code length 48, obtaining version information after LDPC decoding, wherein the first 5 bits are version numbers, the last 17 bits are 24 times l of the length of the information to be decoded, obtaining the length LLEn of the information to be decoded as l × 24, and the last two bits are the error correction Level of the information to be decoded.

In step 206, LDPC decoding is performed on the soft-output valid information array sout except for the version information. FIG. 4 is a flow chart of a standard LDPC decoding. And generating a template matrix Hbm by using the code length and the code rate, and circularly right shifting the unit matrix on the basis of the template matrix to obtain a check matrix H. And decoding by adopting a minimum sum algorithm, wherein when the product of the check matrix and the transposed matrix of the input code word c is a zero matrix, the decoding is successful. And intercepting and returning information bits according to the code rate.

When LLEn exceeds 2304, decoding is performed according to the section with the longest length of 2304, the code rates are unified to R, and R is determined by Level and is the same as step 107. And obtaining the decoding array data through LDPC decoding. In this step, in order to reduce the amount of calculation, the LDPC decoding employs a min-sum SPA algorithm, which is a simplification of the BP decoding algorithm. The transmission form of the message in the BP decoding algorithm is Log-Likelihood Ratio (LLR), and LLRs are transmitted along edges between variable nodes and constraint nodes, so that decision information about the variable nodes is provided in each decoding iteration. Meanwhile, in order to improve the accuracy, a correction factor b is increased, and b is equal to 0.15.

The specific decoding process can refer to: sarah J.Johnson, detail Low-sensitivity part-Check Codes 2.3 Sum-product decoding.

Step 207, intercepting the header information. And analyzing the decoding array data, wherein the first 4 bits are coding type values v, and the next 3 bits are compression type values ctype. When the ctype is 0, fixed-length compression is adopted, the last 16 bits indicate the number n of compressed bytes, and then compressed information is obtained. When the ctype is 1, adopting Huffman compression, then 12 bits represent the number cp of nodes of the Huffman tree, next 16 bits represent the number n of compressed bytes, and then the Huffman tree and variable length information follow.

And step 208, decompressing. And decompressing the decoding array data according to the compression type value ctype. And when ctype is 0, intercepting one byte from each block bit to generate a decompression array BData, and traversing the decompression array BData to restore the initial value according to the coding type v. When ctype is 1, Huffman decoding is performed to generate a decompression array BData. During Huffman decoding, Huffman tree storage information is obtained, nodes are sequentially traversed, and the Huffman tree is reconstructed according to the subsequent traversal and the value of the node degree: if the flag bit is 1, restoring the node information to 8 bits according to the coding type v, and then storing; if the flag bit is 0, the node information is abandoned, and the two-bit node degree is directly extracted.

In step 209, a character string is generated. And setting different character sets according to different coding types, and converting the decompression BData into character strings. But if the coding type is the Byte type, the array BData is directly returned, and the transcoding is not carried out.

While the invention has been described with reference to one or more exemplary embodiments, it will be understood by those skilled in the art that various changes may be made and equivalents may be substituted for elements thereof without departing from the scope of the invention. In addition, many modifications may be made to adapt a particular situation or condition to the teachings of the disclosure without departing from the essential scope thereof. Therefore, it is intended that the invention not be limited to the particular embodiment disclosed as the best mode contemplated for carrying out this invention, but that the disclosed method of encoding and decoding a two-dimensional barcode will include all embodiments falling within the scope of the present invention.

Claims

1. A coding method of two-dimensional bar code, which is used to output the input original binary data information to the two-dimensional bar code that can be attached on the carrier through the coding compression method based on the low density parity check code (LDPC), characterized in that it includes the following steps:

F. setting a flag bit and generating a two-dimensional bar code image.

2. The encoding method of two-dimensional barcode according to claim 1, wherein the input information of step a can support 6 encoding types of numbers, letters, ASCII codes, Byte, kanji CN and UTF 8.

3. The encoding method of a two-dimensional barcode according to claim 1, wherein the step B comprises:

b1, performing Huffman variable length compression on the input information of the byte type;

b2, when the sum of the Huffman tree length and the variable length information length obtained in the step B1 is less than or equal to the product of the length of the byte type input information and the number of bits used by the coding type, fixed length compression is used instead.

4. The method of encoding a two-dimensional barcode according to claim 1, wherein the version information of step E is also compressed by LDPC encoding, and the version information is stored in the middle 1/2 of the compressed information.

5. The encoding method of two-dimensional barcode of claim 1, wherein in step F, the flag bits are filled with information 1 of 7 x 7 size at the upper left, upper right and lower left corners of the two-dimensional barcode image and information 0 is added to the periphery thereof, and the lower right corner of the two-dimensional barcode image is filled with only information 1 of 1 x 1 size.

6. The method of encoding a two-dimensional barcode according to claim 1, wherein in step F, the two-dimensional barcode image is adjusted to be non-square according to the pixel size of the original input.

7. A decoding method of two-dimensional bar code, using one-dimensional linear array contact type or non-contact type image sensor to obtain image data of two-dimensional bar code, recovering and outputting binary data information by decoding method based on LDPC, characterized by comprising the following steps:

E. intercepting version information from the effective information;

8. The decoding method of the two-dimensional barcode of claim 7, wherein the step D comprises:

and obtaining the log-likelihood ratio of the binomial distribution by the gray value table look-up of each code element, traversing the effective information, and covering the gray value by using the log-likelihood ratio.

9. The decoding method of the two-dimensional barcode according to claim 7, wherein the step E comprises:

the version information is intercepted at the middle of the valid information 1/2.

10. The decoding method of the two-dimensional barcode according to claim 7, wherein the step H comprises:

when the compression type value is 0, fixed length decoding is carried out; when the compression type value is 1, Huffman variable length decoding is performed.