# Hardware Decoding Accelerator of (73, 37, 13) QR Code for Power Line Carrier in UPIoT

Authors: Jiye Huang; Shanggang Xie; Tongdong Guo; Zhijin Zhao
Journal: Journal of Sensors
 (2021)

---

## Abstract

The proposal of the ubiquitous power Internet of Things (UPIoT) has increased the demand for communication coverage and data collection of smart grid; the quantity and quality of communication networks are facing greater challenges. This brief applies (73, 37, 13) quadratic residue (QR) codes to power line carrier technology to improve the quality of local data communication in UPIoT. In order to improve the decoding performance of the QR codes, an induction method for the error pattern is proposed, which can divide the originally coupled error pattern into six parts and reuse the same module for decoding. This method greatly reduces the resource requirements, so that (73, 37, 13) QR code can be implemented on FPGA hardware. Notably, the hardware architecture is a modular framework, which can fit into an FPGA with different sizes. As an example (73, 37, 13), QR code is implemented on Intel Arria10 FPGA; the experimental result shows that the maximum decoding frequency of this architecture is 21.7 M Hz, which achieves 4121x speedup compared to CPU. Moreover, the proposed architecture benefits from high flexibility, such as modular design and decoding framework in the form of the pipeline which can be seen as an alternative scheme for decoding long-length QR codes.


---

## Body

## 1. Introduction

With the development of power systems, the types and quantities of electrical equipment are increasing rapidly, for example, Energy Storage (ES) is being widely adopted in the grid to meet the needs of intermittent power generation [1]. This brings a growing demand for information sharing [2] and analysing [3] between all nodes in the power grid system. Ubiquitous power Internet of Things (UPIoT) is proposed as an advanced technology in the construction of smart grids. It can integrate the combination of the Internet of Things (IoT) and the power business, efficiently integrate IoT and power system, and improve the information transparency of the power system. The “Ubiquitous” of UPIoT is embodied in the various nodes of the power system (transmission, transformation, distribution, and consumption), that means the real-time interconnection of people, machinery, power networks, and platforms can be achieved at any time [4].UPIoT is proposed based on IoT, so it has a structure similar to the traditional IoT, including perception layer, network layer, platform layer, and application layer [5]. The perception layer is composed of sensors with different functions in each link and node of the power network. The network layer is mainly composed of the internet or the dedicated network, which is responsible for a large amount of information transmission. The platform layer is the data sharing and publishing center. The application layer provides users with data display and control signal transmission function. It is recognized that UPIoT mainly includes three parts [6] of communication, local communication, edge IoT gateway, and remote communication. As an intermediate carrier between the perception layer and the platform layer, the edge IoT gateway assumes the function of gathering data and the local edge fast computing. The remote network is usually implemented by 4G/5G and dedicated networks, while the local communication network can choose wired or microwave wireless networks due to its short distance. The types and quantities of data measured by local sensors in UPIoT will increase greatly with the development of power networks. Therefore, the local transmission network should have the following characteristics:
(i)
Two-way real-time communication capability(ii)
Low power consumption and low cost(iii)
Strong data compatibilityPower line carrier communication (PLC) technology, as a local communication technology, can carry both power and data and has been widely used for high-speed data transmission, even in relatively remote areas [7]. The good characteristics of PLC, such as direct application of power line transmission data, no need to modify the wiring layout, easy implementation, and two-way communication, can meet the basic characteristics of the local transmission network. However, using power carrier line leads to a relatively large attenuation of carrier signal, and the damage to performance from multiple noises is still a challenge. In order to deal with the shortcomings, some researches have proposed Reed-Solomon (RS), Low Density Parity Check (LDPC) [8, 9], Convolution Code (CC), and other advanced codes [10, 11]. In addition, using modulation techniques such as Quadrature Frequency Shift keying (QFSK) and Orthogonal Frequency Division Multiplexing (OFDM) [12] can improve the reliability of the system.The LDPC codes are selected as the channel coding schemes for the data channels in 5G new radios because of its excellent long code error correction performance. In local communication, most of the transmitted signals between the sensors and the IoT gateway are expected to be power status data and control signals, which can be regard as short data; the advantages of Low-Density Parity Check (LDPC) codes cannot reflect due to the dense and short communication data [8]. In recent years, with continuous development, the root-protograph (RP) LDPC code appeared to solve the interruption limitation of the BF channel due to its nontraversal characteristics [9]. The CC decoding has high computational complexity due to the Viterbi algorithm and the use of interleave causes significant end-to-end delay. Reed-Solomon (RS) codes, which are used in many PLCs, will cause a huge amount of calculation when the redundancy is large. Due to the insufficient error correction capability of the channel encoder, the performance of the receiver still cannot achieve satisfactory performance [10]. Therefore, we propose to use quadratic residue (QR) codes [13] to encode data and control signals in front of the PLC channel, and still can use more commonly used modulation methods such as OFDM; it can obtain the following advantages:
(i)
The requirement of transmission power can be reduced in the same environment(ii)
Improve the reliability of communication and thereby improve communication efficiencyThe QR code gains powerful error correction capabilities by increasing the complexity of decoding; although the QR code decoding algorithm has been improved several times, it is still difficult to make a stand out in practical applications due to its unsatisfactory decoding speed. Based on the existing decoding algorithm, difference syndrome (DS) algorithm [14], and optimized decoding algorithm cyclic weight (OCW) [15], we propose a method suitable for digital circuit hardware implementation, which is named as error pattern induction (EPI). By using EPI, we reduce the (73, 37, 13) QR code into 6 parts so that it can use same pipeline processor, and (73,37, 13) QR code can be realized on limited hardware resources. At the same time, we implemented the hardware decoding architecture of (73, 37, 13) QR code on the Intel Arria10 10AX115-U4F45I1SG FPGA platform, achieving a maximum clock frequency (fmax) of 260.42 MHz, which is equivalent to 21.7 MHz decoding frequency.


## 2. QR Code and Decoding Algorithm

The QR code was proposed by E. Prange in 1958 and has excellent error detection and correction capability due to its large minimum Hamming distance [3]. The QR code is defined on the finite field GF2m, and GF2m is a finite field containing 2m elements. The (73, 37, 13) QR code is constructed over GF29, and its quadratic residue set is given by
(1)Q73=l∣l≡x2mod73,1≤x≤732,=1,2,3,4,6,8,9,12,16,18,19,23,24,25,27,32,35,36,37,38,41,46,48,49,50,54,55,57,61,64,65,67,69,70,71,72.Letm be the smallest positive integer which makes 2mmodn=1, and for (73, 37, 13) QR code, m=9. Let α∈GF29 be a root of the primitive polynomial px=x9+x4+1, then α generates all nonzero elements in the finite field GF29. Obviously, 29−1/73=7, so β=α7 is the 73rd root of unity in GF29, and the generator polynomial of the (73, 37, 13) QR code is given by
(2)gx=∏i∈Q73x−βi=x36+x34+x32+x31+x30+x28+x25+x24+x22+x21+x20+x19+x18+x17+x16+x15+x14+x12+x11+x8+x6+x5+x4+x2+x+1.The message part of the (73, 37, 13) QR code is a vector of length 37 and can be expressed by a polynomial asmx=∑i=036mixi. Then, the codeword can be expressed as
(3)cx=mx⋅x36+mx⋅x36modgx=∑i=072cixi,by using systematic coding, where high 37 bits are message bits, expressed as mx⋅x36, and lower 36 bits are parity bits, expressed as mx⋅x36modgx. If the codeword is passed through an additive white Gaussian noise (AWGN) channel, the noise can be expressed as ex=∑i=072eixi, then the received codeword can be expressed as
(4)rx=cx+ex=∑i=072rixi,let sx=rxmodgx=∑i=035sixi, and the sx is called syndrome polynomial.We will describe the decoding algorithms by integrating DS algorithm and OCW algorithm; of course, there are other decoding algorithms such as Berlekamp-Massey (BM) [16], Fast Algebraic Decoding Algorithm (ADA) [17], Syndrome and Syndrome Difference Decoding Algorithm (SSDDA) [18, 19], all of them are implemented in software.For simplicity, split codewordr to a message part rm and a parity part rp, and split decoded codeword dr to a message part drm and a parity part drp. Let ei be an error in the ith bit of rm, and the syndrome corresponds to ei is expressed as si. The syndromes si0≤i≤36 is shown in Table 1.Table 1
Syndromes and error patterns.
siError patterns01000_1111_0010_0010_1110_1000_1001_1110_0011s11001_0001_0110_0111_0011_1001_1010_0010_0101s21010_1101_1110_1100_1001_1011_1101_1010_1001s31101_0100_1111_1011_1101_1111_0010_1011_0001s40010_0110_1101_0101_0101_0110_1100_1000_0001s50100_1101_1010_1010_1010_1101_1001_0000_0010s61001_1011_0101_0101_0101_1011_0010_0000_0100s71011_1001_1000_1000_0101_1110_1101_1110_1011s81111_1100_0011_0010_0101_0101_0010_0011_0101s90111_0111_0100_0110_0100_0010_1101_1000_1001s101110_1110_1000_1100_1000_0101_1011_0001_0010s110101_0010_0011_1011_1110_0011_1111_1100_0111s121010_0100_0111_0111_1100_0111_1111_1000_1110s131100_0111_1100_1101_0110_0111_0110_1111_1111s140000_0000_1011_1000_0010_0110_0100_0001_1101s150000_0001_0111_0000_0100_1100_1000_0011_1010s160000_0010_1110_0000_1001_1001_0000_0111_0100s170000_0101_1100_0001_0011_0010_0000_1110_1000s180000_1011_1000_0010_0110_0100_0001_1101_0000s190001_0111_0000_0100_1100_1000_0011_1010_0000s200010_1110_0000_1001_1001_0000_0111_0100_0000s210101_1100_0001_0011_0010_0000_1110_1000_0000s221011_1000_0010_0110_0100_0001_1101_0000_0000s231111_1111_0110_1110_0110_1011_0011_1110_0011s240111_0001_1111_1110_0011_1110_1110_0010_0101s251110_0011_1111_1100_0111_1101_1100_0100_1010s260100_1000_1101_1010_0001_0011_0001_0111_0111s271001_0001_1011_0100_0010_0110_0010_1110_1110s281010_1100_0100_1010_1010_0100_1100_0011_1111s291101_0111_1011_0111_1010_0001_0001_1001_1101s300010_0000_0100_1101_1010_1010_1010_1101_1001s310100_0000_1001_1011_0101_0101_0101_1011_0010s321000_0001_0011_0110_1010_1010_1011_0110_0100s331000_1101_0100_1111_1011_1101_1111_0010_1011s341001_0101_1011_1101_1001_0011_0111_1011_0101s351010_0100_0101_1001_1100_1110_0110_1000_1001s361100_0111_1001_0001_0111_0100_0100_1111_0001For a received codewordr, the syndrome sr of r is first calculated, then the weight Wsr of the sr is calculated, and the codeword can be decoded by the following steps.Step 1.
IfWsr≤6, all errors of the received codeword r are in rp. Then, the decoded message part drm=rm, and the decoding is completed at this time. If Wsr>6, there is at least one error existing in the message part rm.Step 2.
Calculatesri=sr∧si0≤i≤36 where ‘∧’ means the bit operation XOR, and calculate the weight Wsri of sri. If i exists in the range of 0≤i≤36 such that Wsri≤5, there is only one error in rm, and we can obtain the decoded message part drm=rm∧ei. Then, the decoding is completed at this time, and the calculation complexity of this step is C371. If i does not exist such that Wsri≤5, there are at least two errors in the message part rm.Step 3.
Calculatesrij=sr∧si∧sj0≤i<j≤36, and calculate the weight Wsrij of srij. If i,j exist in the range of 0≤i<j≤36 such that Wsrij≤4, there are two errors in rm, and we can obtain decoded message part drm=rm∧ei∧ej. Then, the decoding is completed at this time, and the calculation complexity of this step is C372. If i,j does not exist which makes Wsrij≤4, there are at least three errors in rm.Step 4.
Calculatesrijk=sr∧si∧sj∧sk0≤i<j<k≤36, and calculate the weight Wsrijk of srijk. If i,j,k exist in the range of 0≤i<j<k≤36 such that Wsrijk≤3, there are three errors in rm, and we can obtain decoded message part drm=rm∧ei∧ej∧ek. Then, the decoding is completed at this time, and the calculation complexity of this step is c373. If i,j,k does not exist which makes Wsrijk≤3, there are at least four errors rm.Step 5.
Cyclic shiftr by 36 bits to left, the result of shifting is expressed as r′. Then, calculate the syndrome sr′ of r′, and calculate the weight Wsr′ of sr′. Repeat steps 1~4, then 4~6 errors in rm can be correct. After these, the decoding is completed. We can infer that the total computational complexity of the DS algorithm is C371+C372+C373∗2.The simulation of QR code is indispensable, 37-bit random message is generated and encoded by (73, 37, 13) QR code. Then, calculate the decoding performance after mixing the encoded signal with Gaussian white noise. The simulation results of different bit error rate (BER) performance are shown in Figure1. We also show the curves of the two RS codes in [20] and the EPI algorithm proposed in this paper. From Figure 1, we can see that QR codes have better performance than RS codes, and QR codes will also have better performance in practical applications. The specific EPI algorithm will be explained in Section 3.Figure 1
BER performance of the two RS codes, the (73, 37, 13) QR algorithm use DS algorithm in [10] and use EPI in this paper.


## 3. Error Pattern Induction Method

In order to improve the decoding speed and ensure the controllability of the decoding time, it is necessary to calculate all the decoding possibilities, then the decoding could be completed within a fixed time. However, the long codeword length of (73, 37, 13) QR code leads to high decoding complexity, and decoding with a full parallel module will result in a great amount of resource consumption. This decoding framework summarizes the error patterns to implement module multiplexing based on DS algorithm; then, we can reduce resource consumption and hardware burden, and we can make it possible to implement in low-cost hardware.


### 3.1. Error Pattern Induction and Classification

Section2 shows that when there are three errors in rm, the decoding complexity is the highest, so we consider to optimize it firstly.


#### 3.1.1. Three-Error Patterns

The number of three-error patterns isc373, a total of 7770 kinds, which can be decomposed into several parts, and we call them as inductive error patterns; the inductive error patterns are shown in Table 2.Table 2
Three-error inductive error patterns.
Inductive error patternsNumberse0e1en2≤n≤3534e0e2en4≤n≤3431e0e3en6≤n≤3328e0e4en8≤n≤3225e0e5en10≤n≤3122e0e6en12≤n≤3019e0e7en14≤n≤2916e0e8en16≤n≤2813e0e9en18≤n≤2710e0e10en20≤n≤267e0e11en22≤n≤254e0e12enn=241Total numbers210From Table2, there are 210 kinds of inductive error pattern. Cyclic shift each pattern to the left by m1≤m≤36 bits so that we can obtain all 210∗37 kinds of three-error patterns, and these patterns are further decomposed to the form of 7770.At this point, the first decomposition is completed, but due to the uneven distribution of the number of errors, the hardware implementation will result in different pipeline lengths, so we need to process the inductive error patterns. As is shown in Table3, we combine the inductive error patterns and divide them into 6 groups to make the patterns evenly distributed, and each combination pattern group has 35 inductive error patterns.Table 3
Three-error combination.
GroupThree-error combination patternsNumbers1e0e1en2≤n≤35,e0e12enn=2434+1=352e0e2en4≤n≤34,e0e11en22≤n≤2531+4=353e0e3en6≤n≤33,e0e9en18≤n≤2728+7=354e0e4en8≤n≤32,e0e9en18≤n≤2725+10=355e0e5en10≤n≤31,e0e8en16≤n≤2822+13=356e0e6en12≤n≤30,e0e7en14≤n≤2919+16=35We call the inductive patterns in the same group as combination patterns and implement them in same pipeline. Then, the three-error patterns are decomposed into the form asC373=7770=6∗35∗37.


#### 3.1.2. Two-Error Patterns

The number of two-error patterns isd_flag_in=0, a total of 666 kinds can be decomposed into the 18 kinds of inductive patterns, expressed as e0en1≤n≤18. Then, we cyclically shift each pattern to the left by m1≤m≤36 bits so that we can get all 18∗36 kinds of two-error patterns.Since the three-error patterns are divided into 6 groups, we also combine two-error patterns into 6 groups to maintain the consistency of the pipeline, and each group has 3 two-error inductive patterns. The two-error combination patterns are shown in Table4.Table 4
Two-error combination patterns.
GroupTwo-error combination patternsNumbers1e0e1,e0e2,e0e332e0e4,e0e5,e0e633e0e7,e0e8,e0e934e0e10,e0e11,e0e1235e0e13,e0e14,e0e1536e0e16,e0e17,e0e183At this point, the two-error patterns are decomposed into the form asC372=6∗3∗37.


#### 3.1.3. Single-Error Pattern

The number of single-error patterns isC371, a total of 37 kinds. It is the minimum error correction unit and can be grouped without decomposing. Since the number 37 cannot be evenly divided, the single-error patterns are divided into 6 groups. Each group has 7 single-error patterns, and no operation is performed in redundant part to ensure the consistency of the pipeline. The single-error division groups are shown in Table 5.Table 5
Single-error combination patterns.
GroupSingle-error combination patternsNumbers1en0≤n≤672en7≤n≤1373en14≤n≤2074en21≤n≤2775en28≤n≤3476enn=351


### 3.2. Error Pattern Traversal and Decoding Framework

Unlike the DS algorithm, the priority of the memory footprint optimization in the FPGA application is not high. Therefore, we propose a decoding framework that separates decoding operation into an error pattern traversal part and a codeword decoding part. We use memory cells to reduce register consumption, which is feasible in FPGA designs.The specific operation of this decoding framework is shown in Section4. After the preprocessing operation, the codeword r/r′ and the flag bit are stored in First Input First Output (FIFO) memory. Then, the codeword r/r′ is calculated to obtain the initial syndrome sr, and we can traversal of all error patterns by sr. When traversing, if the corresponding condition is met (see Section 4 for details), the decoding flag bit denoting as ‘d_flag’ will be set to 1, and the current error pattern denoting as ‘ep1’, ‘ep2’, and ‘ep3’ will be recorded to the register ‘e_reg_out1’, ‘e_reg_out2’, and ‘e_reg_out3’. When the error pattern traversal is completed, decoding will be performed according to the decoding flag bit, the recorded error pattern positions, and the original codeword stored in FIFO.This framework reduces the register consumption of each stage of the pipeline from store 73 bits of entire codeword to store 18 bits of the three error pattern positions (each error pattern position is 6 bits), which greatly reduces the register consumption. The registers saved here can be used for other intermediate amounts of storage to increase the speed of the entire framework.


## 3.1. Error Pattern Induction and Classification

Section2 shows that when there are three errors in rm, the decoding complexity is the highest, so we consider to optimize it firstly.


### 3.1.1. Three-Error Patterns

The number of three-error patterns isc373, a total of 7770 kinds, which can be decomposed into several parts, and we call them as inductive error patterns; the inductive error patterns are shown in Table 2.Table 2
Three-error inductive error patterns.
Inductive error patternsNumberse0e1en2≤n≤3534e0e2en4≤n≤3431e0e3en6≤n≤3328e0e4en8≤n≤3225e0e5en10≤n≤3122e0e6en12≤n≤3019e0e7en14≤n≤2916e0e8en16≤n≤2813e0e9en18≤n≤2710e0e10en20≤n≤267e0e11en22≤n≤254e0e12enn=241Total numbers210From Table2, there are 210 kinds of inductive error pattern. Cyclic shift each pattern to the left by m1≤m≤36 bits so that we can obtain all 210∗37 kinds of three-error patterns, and these patterns are further decomposed to the form of 7770.At this point, the first decomposition is completed, but due to the uneven distribution of the number of errors, the hardware implementation will result in different pipeline lengths, so we need to process the inductive error patterns. As is shown in Table3, we combine the inductive error patterns and divide them into 6 groups to make the patterns evenly distributed, and each combination pattern group has 35 inductive error patterns.Table 3
Three-error combination.
GroupThree-error combination patternsNumbers1e0e1en2≤n≤35,e0e12enn=2434+1=352e0e2en4≤n≤34,e0e11en22≤n≤2531+4=353e0e3en6≤n≤33,e0e9en18≤n≤2728+7=354e0e4en8≤n≤32,e0e9en18≤n≤2725+10=355e0e5en10≤n≤31,e0e8en16≤n≤2822+13=356e0e6en12≤n≤30,e0e7en14≤n≤2919+16=35We call the inductive patterns in the same group as combination patterns and implement them in same pipeline. Then, the three-error patterns are decomposed into the form asC373=7770=6∗35∗37.


### 3.1.2. Two-Error Patterns

The number of two-error patterns isd_flag_in=0, a total of 666 kinds can be decomposed into the 18 kinds of inductive patterns, expressed as e0en1≤n≤18. Then, we cyclically shift each pattern to the left by m1≤m≤36 bits so that we can get all 18∗36 kinds of two-error patterns.Since the three-error patterns are divided into 6 groups, we also combine two-error patterns into 6 groups to maintain the consistency of the pipeline, and each group has 3 two-error inductive patterns. The two-error combination patterns are shown in Table4.Table 4
Two-error combination patterns.
GroupTwo-error combination patternsNumbers1e0e1,e0e2,e0e332e0e4,e0e5,e0e633e0e7,e0e8,e0e934e0e10,e0e11,e0e1235e0e13,e0e14,e0e1536e0e16,e0e17,e0e183At this point, the two-error patterns are decomposed into the form asC372=6∗3∗37.


### 3.1.3. Single-Error Pattern

The number of single-error patterns isC371, a total of 37 kinds. It is the minimum error correction unit and can be grouped without decomposing. Since the number 37 cannot be evenly divided, the single-error patterns are divided into 6 groups. Each group has 7 single-error patterns, and no operation is performed in redundant part to ensure the consistency of the pipeline. The single-error division groups are shown in Table 5.Table 5
Single-error combination patterns.
GroupSingle-error combination patternsNumbers1en0≤n≤672en7≤n≤1373en14≤n≤2074en21≤n≤2775en28≤n≤3476enn=351


## 3.1.1. Three-Error Patterns

The number of three-error patterns isc373, a total of 7770 kinds, which can be decomposed into several parts, and we call them as inductive error patterns; the inductive error patterns are shown in Table 2.Table 2
Three-error inductive error patterns.
Inductive error patternsNumberse0e1en2≤n≤3534e0e2en4≤n≤3431e0e3en6≤n≤3328e0e4en8≤n≤3225e0e5en10≤n≤3122e0e6en12≤n≤3019e0e7en14≤n≤2916e0e8en16≤n≤2813e0e9en18≤n≤2710e0e10en20≤n≤267e0e11en22≤n≤254e0e12enn=241Total numbers210From Table2, there are 210 kinds of inductive error pattern. Cyclic shift each pattern to the left by m1≤m≤36 bits so that we can obtain all 210∗37 kinds of three-error patterns, and these patterns are further decomposed to the form of 7770.At this point, the first decomposition is completed, but due to the uneven distribution of the number of errors, the hardware implementation will result in different pipeline lengths, so we need to process the inductive error patterns. As is shown in Table3, we combine the inductive error patterns and divide them into 6 groups to make the patterns evenly distributed, and each combination pattern group has 35 inductive error patterns.Table 3
Three-error combination.
GroupThree-error combination patternsNumbers1e0e1en2≤n≤35,e0e12enn=2434+1=352e0e2en4≤n≤34,e0e11en22≤n≤2531+4=353e0e3en6≤n≤33,e0e9en18≤n≤2728+7=354e0e4en8≤n≤32,e0e9en18≤n≤2725+10=355e0e5en10≤n≤31,e0e8en16≤n≤2822+13=356e0e6en12≤n≤30,e0e7en14≤n≤2919+16=35We call the inductive patterns in the same group as combination patterns and implement them in same pipeline. Then, the three-error patterns are decomposed into the form asC373=7770=6∗35∗37.


## 3.1.2. Two-Error Patterns

The number of two-error patterns isd_flag_in=0, a total of 666 kinds can be decomposed into the 18 kinds of inductive patterns, expressed as e0en1≤n≤18. Then, we cyclically shift each pattern to the left by m1≤m≤36 bits so that we can get all 18∗36 kinds of two-error patterns.Since the three-error patterns are divided into 6 groups, we also combine two-error patterns into 6 groups to maintain the consistency of the pipeline, and each group has 3 two-error inductive patterns. The two-error combination patterns are shown in Table4.Table 4
Two-error combination patterns.
GroupTwo-error combination patternsNumbers1e0e1,e0e2,e0e332e0e4,e0e5,e0e633e0e7,e0e8,e0e934e0e10,e0e11,e0e1235e0e13,e0e14,e0e1536e0e16,e0e17,e0e183At this point, the two-error patterns are decomposed into the form asC372=6∗3∗37.


## 3.1.3. Single-Error Pattern

The number of single-error patterns isC371, a total of 37 kinds. It is the minimum error correction unit and can be grouped without decomposing. Since the number 37 cannot be evenly divided, the single-error patterns are divided into 6 groups. Each group has 7 single-error patterns, and no operation is performed in redundant part to ensure the consistency of the pipeline. The single-error division groups are shown in Table 5.Table 5
Single-error combination patterns.
GroupSingle-error combination patternsNumbers1en0≤n≤672en7≤n≤1373en14≤n≤2074en21≤n≤2775en28≤n≤3476enn=351


## 3.2. Error Pattern Traversal and Decoding Framework

Unlike the DS algorithm, the priority of the memory footprint optimization in the FPGA application is not high. Therefore, we propose a decoding framework that separates decoding operation into an error pattern traversal part and a codeword decoding part. We use memory cells to reduce register consumption, which is feasible in FPGA designs.The specific operation of this decoding framework is shown in Section4. After the preprocessing operation, the codeword r/r′ and the flag bit are stored in First Input First Output (FIFO) memory. Then, the codeword r/r′ is calculated to obtain the initial syndrome sr, and we can traversal of all error patterns by sr. When traversing, if the corresponding condition is met (see Section 4 for details), the decoding flag bit denoting as ‘d_flag’ will be set to 1, and the current error pattern denoting as ‘ep1’, ‘ep2’, and ‘ep3’ will be recorded to the register ‘e_reg_out1’, ‘e_reg_out2’, and ‘e_reg_out3’. When the error pattern traversal is completed, decoding will be performed according to the decoding flag bit, the recorded error pattern positions, and the original codeword stored in FIFO.This framework reduces the register consumption of each stage of the pipeline from store 73 bits of entire codeword to store 18 bits of the three error pattern positions (each error pattern position is 6 bits), which greatly reduces the register consumption. The registers saved here can be used for other intermediate amounts of storage to increase the speed of the entire framework.


## 4. Hardware Architecture Design

According to Section3, the operations before and after the cyclic shift are the same, so we can implement these two operations in same hardware framework by preprocessing and postprocessing of the received codeword, then we can realize pipeline multiplexing to improve resource utilization and reduce resource consumption. All the error patterns are summarized and divided into 6 parts, then the decoding modules can be multiplexed. We traverse one part each clock, and all the error patterns are traversed by six clocks. The specific modules are as follows.


### 4.1. Code Words Preprocessing Module

Preprocess the input codewordr by the cyclic shift operation, the original codeword r, and the cyclic shifted codeword r′ are given by
(5)r=rm36,rm35,⋯,rm0,rp35,rp34,⋯,rp1,rp0,r′=rm0,rp35,rp34,⋯,rp0,rm36,rm35,⋯,rm1.The specific structure is shown in Figure2; the current data is determined according to the state of preprocessing flag denoted as ‘pre_flag’(0/1); when pre_flag=0, the current data is original codeword r; when pre_flag=1, the current data is cyclic shifted codeword r′. Then, the data sequence r,r′ are input into initial syndrome generation unit one by one. Note that in order to make the figures clear, the clock signal is not shown in the figures below.Figure 2
Preprocessing unit.


### 4.2. Weight Calculation Unit

The weight calculation unit can accumulate the sum ofsi∑i=035si (as shown in Figure 3). In order to reduce the path delay and increase the operation frequency, we divide the S_in into 6 parts and complete the sum operation in 2 steps.Figure 3
Weight calculation unit.In addition, a module identification signal named “Condition” is introduced to make the weight calculation unit to adapt to different modules.In initial syndrome generation module, “flag_out” will be enabled whenWSin≤6.In single-error traversal module, “flag_out” will be enabled whenWSin≤5.In two-error traversal module, “flag_out” will be enabled whenWSin≤4.In three-error traversal module, “flag_out” will be enabled whenWSin≤3.


### 4.3. Syndrome Generation Unit

The syndrome generation unit has two kinds of units, one forsr and another for sri,srij,srijk.The calculation of initial syndrome is given by(6)sr=rp∧rm0⋅s0∧rm1⋅s1∧⋯∧rm36⋅s36.Other syndrome calculations are given by(7)sr,i=sr∧si0≤i≤36,srij=sr∧si∧sj0≤i<j≤36,srijk=sr∧si∧sj∧sk0≤i<j<k≤36,where i,j,k are the error positions of rm.The specific structure is shown in Figure4. The initial syndrome sr is calculated by formula (6) according to rm,rp and syndromes s0~s36. Then, the other syndromes sri,srij, and srijk can be calculated by sr,si,sj, and sk.Figure 4
Syndrome generation unit.According to the algorithm, when the calculation of initial syndromesr is completed, the weight Wsr of the initial syndrome sr is calculated firstly. If Wsr≤6, the decoding flag bit ‘d_flag_init’ is set to 1, the register ‘e_reg_out3’ of the current error pattern is assigned to “40”, which can provide an indication for postprocessing unit to decoding.


### 4.4. Error Traversal Units

The error traversal units are divided into three types according to the number of errors inrm, which are single-error traversal units, two-error traversal units, and three-error traversal units. In order to reduce the consumption of registers in this design, after each traversal unit calculates the weight of the new syndrome, only the current decoding flag bit ‘d_flag_out’, and the current error pattern ‘ep1’, ‘ep2’, ‘ep3’ are recorded instead of direct decoding. After all pattern traversal is completed, decoding is performed by decoding flag bit and the recorded error patterns.


#### 4.4.1. Single-Error Traversal Units

The specific structure is shown in Figure5. According to the input error pattern position ‘ep1’, calculate sr,ep1=sr∧sep1, and calculate the weight Wsr,ep1 of sr,ep1, then the flag bit ‘d_flag_out’ will be given according to Wsr,ep1. Regardless of whether the current error pattern meets the decoding condition, the current error pattern position ‘ep1’ is recorded to ‘ep1_out’, which simplifies the logic and accurately records the error pattern.Figure 5
Single-error traversal unit.


#### 4.4.2. Two-Error Traversal Units

The specific structure is shown in Figure6. According to the input error pattern positions ‘ep1’, ‘ep2’, calculatesr,ep1,ep2=sr∧sep1∧sep2, and calculate the weight Wsr,ep1,ep2 of sr,ep1,ep2. Then, the flag bit ‘d_flag_out’ will be given according to Wsr,ep1,ep2. At the same time, the current error pattern positions ‘ep1’, ‘ep2’ are recorded to ‘e_reg_out1’, ‘e_reg_out2’.Figure 6
Two-error traversal unit.


#### 4.4.3. Three-Error Traversal Units

The specific structure is shown in Figure7. According to the input error pattern positions ‘ep1’, ‘ep2’, ‘ep3’, calculate sr,ep1,ep2,ep3=sr∧sep1∧sep2∧sep3, and calculate the weight Wsr,ep1,ep2,ep3 of sr,ep1,ep2,ep3. Then, the flag bit ‘d_flag_out’ will be given according to Wsr,ep1,ep2,ep3. At the same time, the current error pattern positions ‘ep1’, ‘ep2’, ‘ep3’ are recorded to ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’.Figure 7
Three-error traversal unit.


### 4.5. Error Traversal Modules

Each error traversal module can complete one kind of error traversal. To facilitate pipeline implementation, the error traversal units need to be integrated. An appropriate integration method can improve resource utilization and improve the running speed of the entire system.


#### 4.5.1. Three-Error Traversal Module

The inductive error patterns are combined according to Table3. After combining, the number of each combination pattern is 35. At this time, module multiplexing can be performed by controlling the value of the input parameter ‘pctr’. In each clock, we traverse 35 kinds of inductive error patterns; all three-error patterns will be finished in 6 clocks (as is shown in Table 6).Table 6
Traversal the error patterns.
pctrThree-error combination patternsTwo-error combination patternsSingle-error combination patterns1e0e1en2≤n≤35e0e12enn=24e0e1,e0e2,e0e3en0≤n≤62e0e2en4≤n≤34e0e11en22≤n≤25e0e4,e0e5,e0e6en7≤n≤133e0e3en6≤n≤33e0e9en18≤n≤27e0e7,e0e8,e0e9en14≤n≤204e0e4en8≤n≤32e0e9en18≤n≤27e0e10,e0e11,e0e12en21≤n≤275e0e5en10≤n≤31e0e8en16≤n≤28e0e13,e0e14,e0e15en28≤n≤346e0e6en12≤n≤30e0e7en14≤n≤29e0e16,e0e17,e0e18enn=35Change the input parameter ‘pctr’ 1≤pctr≤6 to control the switching of the combination patterns, and according to the offset parameter ‘poff’ 0≤poff≤34, we can determine the initialization pattern einit1einit2einit3 to construct the basic pipeline unit. The calculation method of the initialization parameter is given by
(8)init1=0,init2=13−pctr,whenpctr∗2+poff>36−pctr,pctr,whenpctr∗2+poff<36−pctr,init3=pctr+poff−11,whenpctr∗2+poff>36−pctr,pctr∗2+poff,whenpctr∗2+poff<36−pctr.According to the input decoding flag bit ‘d_flag_in’, if d_flag_in=1, the error pattern of the previous stage traversal unit has met the decoding condition, set ‘d_flag_out’ to 1, and register ‘e_reg_in1’, ‘e_reg_in2’, ‘e_reg_in3’ directly to ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’; if d_flag_in=0, the error pattern of the previous stage traversal unit does not meet the decoding condition, and the error pattern traversal result of this level is considered.The specific structure of the basic pipeline unit is shown in Figure8(a). The initial error positions ‘e_init1’, ‘e_init2’, ‘e_init3’ are determined according to the parameters ‘pctr’ and ‘poff’. Then, modulo 36 plus l0≤l≤36 bits, respectively, with initial error positions to obtain new error patterns for traversal. Combined with the input initial syndrome sr, 37 error traversal units are obtained to form a basic pipeline unit. After traversing these error patterns, the 37 results of traversal are judged and selected. If the error patterns in this unit satisfy the decoding condition, the ‘d_flag_out’ is assigned to 1, and the current error positions are output to the error pattern record registers ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’. Then, the input initial syndrome sr is passed to the next level for traversal.Figure 8
(a) Three-error traversal pipeline unit; (b) three-error traversal module.
(a)(b)35 three-error traversal pipeline units are connected step by step to form a complete three-error traversal module. The specific structure is shown in Figure8(b). The initial syndrome sr, parameter ‘pctr’, decoding flag ‘d_flag_out’ and error pattern record register ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’ are passed in stages to ensure the integrity of the error pattern traversal and the stability of the data.


#### 4.5.2. Two-Error Traversal Module

In the three-error traversal pipeline unit, all three-error patterns have been distributed by 6 clocks, so we also distribute all two-error patterns into 6 clocks. In each clock, we traverse 3 inductive two-error patterns, all two-error patterns will be finished in 6 clocks (as shown in Table6).Change the input parameter ‘pctr’ 1≤pctr≤6 to control the switching of the combination patterns, and according to the offset parameter ‘poff’ 0≤poff≤3, we can determine the initialization pattern einit1einit2 to construct the basic pipeline unit. The calculation method of the initialization pattern is given by
(9)init1=0,init2=pctr∗3+poff−3.According to the input decoding flag bit ‘d_flag_in’, if d_flag_in=1, the error pattern of the previous stage traversal unit has met the decoding condition, set ‘d_flag_out’ to 1, and register ‘e_reg_in1’, ‘e_reg_in2’, ‘e_reg_in3’ directly to ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’; if d_flag_in=0, the error pattern of the previous stage traversal unit does not meet the decoding condition, and the error pattern traversal result of this level is considered.The specific structure is as shown in Figure9(a), and the initial error positions ‘e_init1’, ‘e_init2’ are determined according to the parameters ‘pctr’ and ‘poff’. Then, modulo 36 plus l0≤l≤36 bits, respectively, with initial error positions to obtain new error patterns for traversal. Combined with the input initial syndrome sr, 37 error traversal units are obtained to form a basic pipeline unit. After traversing these error patterns, the 37 results of traversal are judged and selected. If the error patterns in this module satisfy the decoding condition, the ‘d_flag_out’ is assigned to 1, the current error positions are output to the error pattern record registers ‘e_reg_out1’, ‘e_reg_out2’, and the value of ‘e_reg_out3’ is set to 42, providing an indication for the postprocessing unit. Then, the input initial syndrome is passed to the next level for traversal.Figure 9
(a) Two-error traversal pipeline unit; (b) three-error traversal module.
(a)(b)Three two-error traversal pipeline units are connected step by step to form a complete two-error traversal module. The specific structure is shown in Figure9(b). The initial syndrome, parameters ‘pctr’, ‘poff’, decoding flag ‘d_flag_out’, and error pattern record registers ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’ are passed in stages to ensure the integrity of the error pattern traversal and the stability of the data.


#### 4.5.3. Single-Error Traversal Module

The same as three-error and two-error traversal pipeline unit, all the single-error traversal units are distributed to 6 clocks (as shown in Table6).Change the input parameter ‘pctr’1≤pctr≤6 to control the switching of the combination patterns, we can determine the initialization pattern einit1 to construct the basic pipeline unit. The calculation method of the initialization pattern is given by
(10)init1=para_ctrl−1∗7.According to the input decoding flag bit ‘d_flag_in’, ifd_flag_in=1, the error pattern of the previous stage traversal unit has met the decoding condition, set ‘d_flag_out’ to 1, and register ‘e_reg_in1’, ‘e_reg_in2’, ‘e_reg_in3’ directly to ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’; if d_flag_in=0, the error pattern of the previous stage traversal unit does not meet the decoding condition, and the error pattern traversal result of this level is considered.The specific structure is as shown in Figure10, and the initial error position ‘e_init1’ is determined according to the parameter ‘pctr’. Then, modulo 36 plus l0≤l≤36 bits, respectively, with initial error position to obtain new error patterns for traversal. Combined with the input initial syndrome sr, 7 single-error traversal units are obtained to form a complete single-error traversal module.Figure 10
Single-error traversal pipeline unit.After traversing the error patterns, the 7 results of traversal are judged and selected. If the error patterns satisfy the decoding condition in this module, the ‘d_flag_out’ is set to 1, the current error positions are output to the error pattern record registers ‘err_reg_out1’. And ‘err_reg_out2’ is set to 0, ‘err_reg_out3’ is set to 41, which provide indications for postprocessing unit. Then, the input initial syndromesr is passed for final decoding.


### 4.6. Decoding and Postprocessing Unit

Read the data stored in the FIFO, denoted as ‘r_delay’ and ‘pre_flag_delay’, and ‘r_delay’ contains a message part ‘m_delay’ and a parity part ‘p_delay’. According to the decoding status flag bit ‘d_flag1’, error pattern record registers ‘e_reg_out11’, ‘e_reg_out12’, ‘e_reg_out13’, preprocessing status flag bit ‘pre_flag_delay’ and the pipeline passed syndrome ‘s_delay’, the decoding can be completed. Denote the decoded codeword message part as ‘m_decode’ and denote decoded codeword parity part ‘p_decode’. The operations of decoding are shown in Table7.Table 7
Decoding operations.
e_reg_out3m_decodep_decode40m_delayp_delay∧s_delay41m_delay∧ee_reg1p_delay∧s_delay∧se_reg142m_delay∧ee_reg1∧ee_reg2p_delay∧s_delay∧se_reg1∧se_reg20~36m_delay∧ee_reg1∧ee_reg2∧ee_reg3p_delay∧s_delay∧se_reg1∧se_reg2∧se_reg3After the decoding is completed, postprocessing is required to restore the original codeword order. The decoded codeword is cyclically shifted and restored according to the preprocessing status register ‘pre_flag_delay’, thereby we can obtain the final decoded codeword ‘m_final’ as
(11)m_final=m_decode,whenpre_flag_delay=0,p_decode,m_decode36,whenpre_flag_delay=1.At this time, the decoding is completed, ‘m_final’ is the final decoded codeword, and the specific structure is as shown in Figure11.Figure 11
Decoding and postprocessing unit.


### 4.7. Pipeline Architecture

The preprocessing module, the initial syndrome generation module, the three-error traversal module, the two-error traversal module, the single-error traversal module, and the decoding and postprocessing module are connected step by step to form a 42-stage pipeline. The specific architecture is shown in Figure12.Figure 12
Pipeline architecture.


### 4.8. Hardware Implementation Results

The experiment and verification are divided into two parts, software verification and hardware verification. Software verification tests the performance of QR codes while hardware verification tests the acceleration effects of QR codes. Software verification part is carried out on the Personal Computer (PC), which is also mentioned in Section2. The verification software runs in VS2019, Intel core I5-6500, windows 10 environment, and the decoding time is shown in Table 8. In order to show the difference between various decoding algorithms, we have recorded the decoding error correction time of various decoding algorithms under different number of errors. There is no doubt that the more errors an encoded message has, the longer decoding time cost, and the unstable decoding delay will have an impact on the real-time performance of the IOT device. In addition, the software experiment content also included the average decoding time of various decoding algorithms by calculating average based on the probability distribution of the number of errors, the results can be used as a reference for the real-time performance of decoding algorithms.Table 8
Decoding time under various conditions.
EnvironmentWorksError numbers (us)Average 1Average 2123456PCDS in this paper1.122.164.2419.7648.36203.66190.003.863IFBM in [17]205.5142.7219.32955.93104.61182411065.57378.42ADA in [18]1.877117.41271.391269.36536.315954.55482.6649.97SSDDA in [19]1.70022.537822.863286.47482.94701.54681.2726.4Algorithm in [20]1134184826116822114173091529193.322089DS in [14]0.8545.6938.395.8198245240.269116.02Arria10Hardware implemented in this paper0.04610.04610.04610.04610.04610.04610.04610.0461Note that the average decoding time 1 is calculated by supposing all error patterns have the same probability of occurrence. And the average decoding time 2 is calculated by supposing there must be 1~5 errors in the received code and is under the environment of 7 dB SNR, where the occurring probability is 41.27% of one error, 36.49% of two errors, 15.92% of three errors, 5.03% of four errors, 1.1% of five errors, and 0.2% of six errors.The hardware verification framework is shown in Figure13. Random messages and noise are generated by ROM lookup table. The sum of encoded message and noise will input into the decoding accelerator. The BER counter records the error rate by comparing the decoding result with the original message.Figure 13
Hardware experimental framework.The decoding accelerator is deployed in Intel Arria10 10AX115U4F45I1SG FPGA; the results is given in the Table9.Table 9
Results of accelerator.
AvailableResultALMs43.72 k12.7 kBlock RAM55.6 Mbit0.15 MbitMax clock freq.—260.42 MHzLatency—46.07 nsIn this decoding framework, all error patterns are evenly distributed into the pipeline, so the decoding time is fixed. A complete decoding requires 125 clocks, the traverse modules cost 12 clocks, 6 clocks to traverse all patterns, and 6 clocks repeated after shifting. Therefore, after 12 clocks of pipeline processing, a valid decoding result can be obtained. At the operation frequency of 260.42 M Hz, every 12 clock outputs can be equivalent to a decoding speed of 21.7 M Hz, the decoding time is 46.07 ns, and the decoding time required of each condition is shown in Table8. Compared with PC, hardware decoding acceleration can obtain 4121 times of decoding speed increase and can maintain a constant decoding time.


## 4.1. Code Words Preprocessing Module

Preprocess the input codewordr by the cyclic shift operation, the original codeword r, and the cyclic shifted codeword r′ are given by
(5)r=rm36,rm35,⋯,rm0,rp35,rp34,⋯,rp1,rp0,r′=rm0,rp35,rp34,⋯,rp0,rm36,rm35,⋯,rm1.The specific structure is shown in Figure2; the current data is determined according to the state of preprocessing flag denoted as ‘pre_flag’(0/1); when pre_flag=0, the current data is original codeword r; when pre_flag=1, the current data is cyclic shifted codeword r′. Then, the data sequence r,r′ are input into initial syndrome generation unit one by one. Note that in order to make the figures clear, the clock signal is not shown in the figures below.Figure 2
Preprocessing unit.


## 4.2. Weight Calculation Unit

The weight calculation unit can accumulate the sum ofsi∑i=035si (as shown in Figure 3). In order to reduce the path delay and increase the operation frequency, we divide the S_in into 6 parts and complete the sum operation in 2 steps.Figure 3
Weight calculation unit.In addition, a module identification signal named “Condition” is introduced to make the weight calculation unit to adapt to different modules.In initial syndrome generation module, “flag_out” will be enabled whenWSin≤6.In single-error traversal module, “flag_out” will be enabled whenWSin≤5.In two-error traversal module, “flag_out” will be enabled whenWSin≤4.In three-error traversal module, “flag_out” will be enabled whenWSin≤3.


## 4.3. Syndrome Generation Unit

The syndrome generation unit has two kinds of units, one forsr and another for sri,srij,srijk.The calculation of initial syndrome is given by(6)sr=rp∧rm0⋅s0∧rm1⋅s1∧⋯∧rm36⋅s36.Other syndrome calculations are given by(7)sr,i=sr∧si0≤i≤36,srij=sr∧si∧sj0≤i<j≤36,srijk=sr∧si∧sj∧sk0≤i<j<k≤36,where i,j,k are the error positions of rm.The specific structure is shown in Figure4. The initial syndrome sr is calculated by formula (6) according to rm,rp and syndromes s0~s36. Then, the other syndromes sri,srij, and srijk can be calculated by sr,si,sj, and sk.Figure 4
Syndrome generation unit.According to the algorithm, when the calculation of initial syndromesr is completed, the weight Wsr of the initial syndrome sr is calculated firstly. If Wsr≤6, the decoding flag bit ‘d_flag_init’ is set to 1, the register ‘e_reg_out3’ of the current error pattern is assigned to “40”, which can provide an indication for postprocessing unit to decoding.


## 4.4. Error Traversal Units

The error traversal units are divided into three types according to the number of errors inrm, which are single-error traversal units, two-error traversal units, and three-error traversal units. In order to reduce the consumption of registers in this design, after each traversal unit calculates the weight of the new syndrome, only the current decoding flag bit ‘d_flag_out’, and the current error pattern ‘ep1’, ‘ep2’, ‘ep3’ are recorded instead of direct decoding. After all pattern traversal is completed, decoding is performed by decoding flag bit and the recorded error patterns.


### 4.4.1. Single-Error Traversal Units

The specific structure is shown in Figure5. According to the input error pattern position ‘ep1’, calculate sr,ep1=sr∧sep1, and calculate the weight Wsr,ep1 of sr,ep1, then the flag bit ‘d_flag_out’ will be given according to Wsr,ep1. Regardless of whether the current error pattern meets the decoding condition, the current error pattern position ‘ep1’ is recorded to ‘ep1_out’, which simplifies the logic and accurately records the error pattern.Figure 5
Single-error traversal unit.


### 4.4.2. Two-Error Traversal Units

The specific structure is shown in Figure6. According to the input error pattern positions ‘ep1’, ‘ep2’, calculatesr,ep1,ep2=sr∧sep1∧sep2, and calculate the weight Wsr,ep1,ep2 of sr,ep1,ep2. Then, the flag bit ‘d_flag_out’ will be given according to Wsr,ep1,ep2. At the same time, the current error pattern positions ‘ep1’, ‘ep2’ are recorded to ‘e_reg_out1’, ‘e_reg_out2’.Figure 6
Two-error traversal unit.


### 4.4.3. Three-Error Traversal Units

The specific structure is shown in Figure7. According to the input error pattern positions ‘ep1’, ‘ep2’, ‘ep3’, calculate sr,ep1,ep2,ep3=sr∧sep1∧sep2∧sep3, and calculate the weight Wsr,ep1,ep2,ep3 of sr,ep1,ep2,ep3. Then, the flag bit ‘d_flag_out’ will be given according to Wsr,ep1,ep2,ep3. At the same time, the current error pattern positions ‘ep1’, ‘ep2’, ‘ep3’ are recorded to ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’.Figure 7
Three-error traversal unit.


## 4.4.1. Single-Error Traversal Units

The specific structure is shown in Figure5. According to the input error pattern position ‘ep1’, calculate sr,ep1=sr∧sep1, and calculate the weight Wsr,ep1 of sr,ep1, then the flag bit ‘d_flag_out’ will be given according to Wsr,ep1. Regardless of whether the current error pattern meets the decoding condition, the current error pattern position ‘ep1’ is recorded to ‘ep1_out’, which simplifies the logic and accurately records the error pattern.Figure 5
Single-error traversal unit.


## 4.4.2. Two-Error Traversal Units

The specific structure is shown in Figure6. According to the input error pattern positions ‘ep1’, ‘ep2’, calculatesr,ep1,ep2=sr∧sep1∧sep2, and calculate the weight Wsr,ep1,ep2 of sr,ep1,ep2. Then, the flag bit ‘d_flag_out’ will be given according to Wsr,ep1,ep2. At the same time, the current error pattern positions ‘ep1’, ‘ep2’ are recorded to ‘e_reg_out1’, ‘e_reg_out2’.Figure 6
Two-error traversal unit.


## 4.4.3. Three-Error Traversal Units

The specific structure is shown in Figure7. According to the input error pattern positions ‘ep1’, ‘ep2’, ‘ep3’, calculate sr,ep1,ep2,ep3=sr∧sep1∧sep2∧sep3, and calculate the weight Wsr,ep1,ep2,ep3 of sr,ep1,ep2,ep3. Then, the flag bit ‘d_flag_out’ will be given according to Wsr,ep1,ep2,ep3. At the same time, the current error pattern positions ‘ep1’, ‘ep2’, ‘ep3’ are recorded to ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’.Figure 7
Three-error traversal unit.


## 4.5. Error Traversal Modules

Each error traversal module can complete one kind of error traversal. To facilitate pipeline implementation, the error traversal units need to be integrated. An appropriate integration method can improve resource utilization and improve the running speed of the entire system.


### 4.5.1. Three-Error Traversal Module

The inductive error patterns are combined according to Table3. After combining, the number of each combination pattern is 35. At this time, module multiplexing can be performed by controlling the value of the input parameter ‘pctr’. In each clock, we traverse 35 kinds of inductive error patterns; all three-error patterns will be finished in 6 clocks (as is shown in Table 6).Table 6
Traversal the error patterns.
pctrThree-error combination patternsTwo-error combination patternsSingle-error combination patterns1e0e1en2≤n≤35e0e12enn=24e0e1,e0e2,e0e3en0≤n≤62e0e2en4≤n≤34e0e11en22≤n≤25e0e4,e0e5,e0e6en7≤n≤133e0e3en6≤n≤33e0e9en18≤n≤27e0e7,e0e8,e0e9en14≤n≤204e0e4en8≤n≤32e0e9en18≤n≤27e0e10,e0e11,e0e12en21≤n≤275e0e5en10≤n≤31e0e8en16≤n≤28e0e13,e0e14,e0e15en28≤n≤346e0e6en12≤n≤30e0e7en14≤n≤29e0e16,e0e17,e0e18enn=35Change the input parameter ‘pctr’ 1≤pctr≤6 to control the switching of the combination patterns, and according to the offset parameter ‘poff’ 0≤poff≤34, we can determine the initialization pattern einit1einit2einit3 to construct the basic pipeline unit. The calculation method of the initialization parameter is given by
(8)init1=0,init2=13−pctr,whenpctr∗2+poff>36−pctr,pctr,whenpctr∗2+poff<36−pctr,init3=pctr+poff−11,whenpctr∗2+poff>36−pctr,pctr∗2+poff,whenpctr∗2+poff<36−pctr.According to the input decoding flag bit ‘d_flag_in’, if d_flag_in=1, the error pattern of the previous stage traversal unit has met the decoding condition, set ‘d_flag_out’ to 1, and register ‘e_reg_in1’, ‘e_reg_in2’, ‘e_reg_in3’ directly to ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’; if d_flag_in=0, the error pattern of the previous stage traversal unit does not meet the decoding condition, and the error pattern traversal result of this level is considered.The specific structure of the basic pipeline unit is shown in Figure8(a). The initial error positions ‘e_init1’, ‘e_init2’, ‘e_init3’ are determined according to the parameters ‘pctr’ and ‘poff’. Then, modulo 36 plus l0≤l≤36 bits, respectively, with initial error positions to obtain new error patterns for traversal. Combined with the input initial syndrome sr, 37 error traversal units are obtained to form a basic pipeline unit. After traversing these error patterns, the 37 results of traversal are judged and selected. If the error patterns in this unit satisfy the decoding condition, the ‘d_flag_out’ is assigned to 1, and the current error positions are output to the error pattern record registers ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’. Then, the input initial syndrome sr is passed to the next level for traversal.Figure 8
(a) Three-error traversal pipeline unit; (b) three-error traversal module.
(a)(b)35 three-error traversal pipeline units are connected step by step to form a complete three-error traversal module. The specific structure is shown in Figure8(b). The initial syndrome sr, parameter ‘pctr’, decoding flag ‘d_flag_out’ and error pattern record register ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’ are passed in stages to ensure the integrity of the error pattern traversal and the stability of the data.


### 4.5.2. Two-Error Traversal Module

In the three-error traversal pipeline unit, all three-error patterns have been distributed by 6 clocks, so we also distribute all two-error patterns into 6 clocks. In each clock, we traverse 3 inductive two-error patterns, all two-error patterns will be finished in 6 clocks (as shown in Table6).Change the input parameter ‘pctr’ 1≤pctr≤6 to control the switching of the combination patterns, and according to the offset parameter ‘poff’ 0≤poff≤3, we can determine the initialization pattern einit1einit2 to construct the basic pipeline unit. The calculation method of the initialization pattern is given by
(9)init1=0,init2=pctr∗3+poff−3.According to the input decoding flag bit ‘d_flag_in’, if d_flag_in=1, the error pattern of the previous stage traversal unit has met the decoding condition, set ‘d_flag_out’ to 1, and register ‘e_reg_in1’, ‘e_reg_in2’, ‘e_reg_in3’ directly to ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’; if d_flag_in=0, the error pattern of the previous stage traversal unit does not meet the decoding condition, and the error pattern traversal result of this level is considered.The specific structure is as shown in Figure9(a), and the initial error positions ‘e_init1’, ‘e_init2’ are determined according to the parameters ‘pctr’ and ‘poff’. Then, modulo 36 plus l0≤l≤36 bits, respectively, with initial error positions to obtain new error patterns for traversal. Combined with the input initial syndrome sr, 37 error traversal units are obtained to form a basic pipeline unit. After traversing these error patterns, the 37 results of traversal are judged and selected. If the error patterns in this module satisfy the decoding condition, the ‘d_flag_out’ is assigned to 1, the current error positions are output to the error pattern record registers ‘e_reg_out1’, ‘e_reg_out2’, and the value of ‘e_reg_out3’ is set to 42, providing an indication for the postprocessing unit. Then, the input initial syndrome is passed to the next level for traversal.Figure 9
(a) Two-error traversal pipeline unit; (b) three-error traversal module.
(a)(b)Three two-error traversal pipeline units are connected step by step to form a complete two-error traversal module. The specific structure is shown in Figure9(b). The initial syndrome, parameters ‘pctr’, ‘poff’, decoding flag ‘d_flag_out’, and error pattern record registers ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’ are passed in stages to ensure the integrity of the error pattern traversal and the stability of the data.


### 4.5.3. Single-Error Traversal Module

The same as three-error and two-error traversal pipeline unit, all the single-error traversal units are distributed to 6 clocks (as shown in Table6).Change the input parameter ‘pctr’1≤pctr≤6 to control the switching of the combination patterns, we can determine the initialization pattern einit1 to construct the basic pipeline unit. The calculation method of the initialization pattern is given by
(10)init1=para_ctrl−1∗7.According to the input decoding flag bit ‘d_flag_in’, ifd_flag_in=1, the error pattern of the previous stage traversal unit has met the decoding condition, set ‘d_flag_out’ to 1, and register ‘e_reg_in1’, ‘e_reg_in2’, ‘e_reg_in3’ directly to ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’; if d_flag_in=0, the error pattern of the previous stage traversal unit does not meet the decoding condition, and the error pattern traversal result of this level is considered.The specific structure is as shown in Figure10, and the initial error position ‘e_init1’ is determined according to the parameter ‘pctr’. Then, modulo 36 plus l0≤l≤36 bits, respectively, with initial error position to obtain new error patterns for traversal. Combined with the input initial syndrome sr, 7 single-error traversal units are obtained to form a complete single-error traversal module.Figure 10
Single-error traversal pipeline unit.After traversing the error patterns, the 7 results of traversal are judged and selected. If the error patterns satisfy the decoding condition in this module, the ‘d_flag_out’ is set to 1, the current error positions are output to the error pattern record registers ‘err_reg_out1’. And ‘err_reg_out2’ is set to 0, ‘err_reg_out3’ is set to 41, which provide indications for postprocessing unit. Then, the input initial syndromesr is passed for final decoding.


## 4.5.1. Three-Error Traversal Module

The inductive error patterns are combined according to Table3. After combining, the number of each combination pattern is 35. At this time, module multiplexing can be performed by controlling the value of the input parameter ‘pctr’. In each clock, we traverse 35 kinds of inductive error patterns; all three-error patterns will be finished in 6 clocks (as is shown in Table 6).Table 6
Traversal the error patterns.
pctrThree-error combination patternsTwo-error combination patternsSingle-error combination patterns1e0e1en2≤n≤35e0e12enn=24e0e1,e0e2,e0e3en0≤n≤62e0e2en4≤n≤34e0e11en22≤n≤25e0e4,e0e5,e0e6en7≤n≤133e0e3en6≤n≤33e0e9en18≤n≤27e0e7,e0e8,e0e9en14≤n≤204e0e4en8≤n≤32e0e9en18≤n≤27e0e10,e0e11,e0e12en21≤n≤275e0e5en10≤n≤31e0e8en16≤n≤28e0e13,e0e14,e0e15en28≤n≤346e0e6en12≤n≤30e0e7en14≤n≤29e0e16,e0e17,e0e18enn=35Change the input parameter ‘pctr’ 1≤pctr≤6 to control the switching of the combination patterns, and according to the offset parameter ‘poff’ 0≤poff≤34, we can determine the initialization pattern einit1einit2einit3 to construct the basic pipeline unit. The calculation method of the initialization parameter is given by
(8)init1=0,init2=13−pctr,whenpctr∗2+poff>36−pctr,pctr,whenpctr∗2+poff<36−pctr,init3=pctr+poff−11,whenpctr∗2+poff>36−pctr,pctr∗2+poff,whenpctr∗2+poff<36−pctr.According to the input decoding flag bit ‘d_flag_in’, if d_flag_in=1, the error pattern of the previous stage traversal unit has met the decoding condition, set ‘d_flag_out’ to 1, and register ‘e_reg_in1’, ‘e_reg_in2’, ‘e_reg_in3’ directly to ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’; if d_flag_in=0, the error pattern of the previous stage traversal unit does not meet the decoding condition, and the error pattern traversal result of this level is considered.The specific structure of the basic pipeline unit is shown in Figure8(a). The initial error positions ‘e_init1’, ‘e_init2’, ‘e_init3’ are determined according to the parameters ‘pctr’ and ‘poff’. Then, modulo 36 plus l0≤l≤36 bits, respectively, with initial error positions to obtain new error patterns for traversal. Combined with the input initial syndrome sr, 37 error traversal units are obtained to form a basic pipeline unit. After traversing these error patterns, the 37 results of traversal are judged and selected. If the error patterns in this unit satisfy the decoding condition, the ‘d_flag_out’ is assigned to 1, and the current error positions are output to the error pattern record registers ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’. Then, the input initial syndrome sr is passed to the next level for traversal.Figure 8
(a) Three-error traversal pipeline unit; (b) three-error traversal module.
(a)(b)35 three-error traversal pipeline units are connected step by step to form a complete three-error traversal module. The specific structure is shown in Figure8(b). The initial syndrome sr, parameter ‘pctr’, decoding flag ‘d_flag_out’ and error pattern record register ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’ are passed in stages to ensure the integrity of the error pattern traversal and the stability of the data.


## 4.5.2. Two-Error Traversal Module

In the three-error traversal pipeline unit, all three-error patterns have been distributed by 6 clocks, so we also distribute all two-error patterns into 6 clocks. In each clock, we traverse 3 inductive two-error patterns, all two-error patterns will be finished in 6 clocks (as shown in Table6).Change the input parameter ‘pctr’ 1≤pctr≤6 to control the switching of the combination patterns, and according to the offset parameter ‘poff’ 0≤poff≤3, we can determine the initialization pattern einit1einit2 to construct the basic pipeline unit. The calculation method of the initialization pattern is given by
(9)init1=0,init2=pctr∗3+poff−3.According to the input decoding flag bit ‘d_flag_in’, if d_flag_in=1, the error pattern of the previous stage traversal unit has met the decoding condition, set ‘d_flag_out’ to 1, and register ‘e_reg_in1’, ‘e_reg_in2’, ‘e_reg_in3’ directly to ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’; if d_flag_in=0, the error pattern of the previous stage traversal unit does not meet the decoding condition, and the error pattern traversal result of this level is considered.The specific structure is as shown in Figure9(a), and the initial error positions ‘e_init1’, ‘e_init2’ are determined according to the parameters ‘pctr’ and ‘poff’. Then, modulo 36 plus l0≤l≤36 bits, respectively, with initial error positions to obtain new error patterns for traversal. Combined with the input initial syndrome sr, 37 error traversal units are obtained to form a basic pipeline unit. After traversing these error patterns, the 37 results of traversal are judged and selected. If the error patterns in this module satisfy the decoding condition, the ‘d_flag_out’ is assigned to 1, the current error positions are output to the error pattern record registers ‘e_reg_out1’, ‘e_reg_out2’, and the value of ‘e_reg_out3’ is set to 42, providing an indication for the postprocessing unit. Then, the input initial syndrome is passed to the next level for traversal.Figure 9
(a) Two-error traversal pipeline unit; (b) three-error traversal module.
(a)(b)Three two-error traversal pipeline units are connected step by step to form a complete two-error traversal module. The specific structure is shown in Figure9(b). The initial syndrome, parameters ‘pctr’, ‘poff’, decoding flag ‘d_flag_out’, and error pattern record registers ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’ are passed in stages to ensure the integrity of the error pattern traversal and the stability of the data.


## 4.5.3. Single-Error Traversal Module

The same as three-error and two-error traversal pipeline unit, all the single-error traversal units are distributed to 6 clocks (as shown in Table6).Change the input parameter ‘pctr’1≤pctr≤6 to control the switching of the combination patterns, we can determine the initialization pattern einit1 to construct the basic pipeline unit. The calculation method of the initialization pattern is given by
(10)init1=para_ctrl−1∗7.According to the input decoding flag bit ‘d_flag_in’, ifd_flag_in=1, the error pattern of the previous stage traversal unit has met the decoding condition, set ‘d_flag_out’ to 1, and register ‘e_reg_in1’, ‘e_reg_in2’, ‘e_reg_in3’ directly to ‘e_reg_out1’, ‘e_reg_out2’, ‘e_reg_out3’; if d_flag_in=0, the error pattern of the previous stage traversal unit does not meet the decoding condition, and the error pattern traversal result of this level is considered.The specific structure is as shown in Figure10, and the initial error position ‘e_init1’ is determined according to the parameter ‘pctr’. Then, modulo 36 plus l0≤l≤36 bits, respectively, with initial error position to obtain new error patterns for traversal. Combined with the input initial syndrome sr, 7 single-error traversal units are obtained to form a complete single-error traversal module.Figure 10
Single-error traversal pipeline unit.After traversing the error patterns, the 7 results of traversal are judged and selected. If the error patterns satisfy the decoding condition in this module, the ‘d_flag_out’ is set to 1, the current error positions are output to the error pattern record registers ‘err_reg_out1’. And ‘err_reg_out2’ is set to 0, ‘err_reg_out3’ is set to 41, which provide indications for postprocessing unit. Then, the input initial syndromesr is passed for final decoding.


## 4.6. Decoding and Postprocessing Unit

Read the data stored in the FIFO, denoted as ‘r_delay’ and ‘pre_flag_delay’, and ‘r_delay’ contains a message part ‘m_delay’ and a parity part ‘p_delay’. According to the decoding status flag bit ‘d_flag1’, error pattern record registers ‘e_reg_out11’, ‘e_reg_out12’, ‘e_reg_out13’, preprocessing status flag bit ‘pre_flag_delay’ and the pipeline passed syndrome ‘s_delay’, the decoding can be completed. Denote the decoded codeword message part as ‘m_decode’ and denote decoded codeword parity part ‘p_decode’. The operations of decoding are shown in Table7.Table 7
Decoding operations.
e_reg_out3m_decodep_decode40m_delayp_delay∧s_delay41m_delay∧ee_reg1p_delay∧s_delay∧se_reg142m_delay∧ee_reg1∧ee_reg2p_delay∧s_delay∧se_reg1∧se_reg20~36m_delay∧ee_reg1∧ee_reg2∧ee_reg3p_delay∧s_delay∧se_reg1∧se_reg2∧se_reg3After the decoding is completed, postprocessing is required to restore the original codeword order. The decoded codeword is cyclically shifted and restored according to the preprocessing status register ‘pre_flag_delay’, thereby we can obtain the final decoded codeword ‘m_final’ as
(11)m_final=m_decode,whenpre_flag_delay=0,p_decode,m_decode36,whenpre_flag_delay=1.At this time, the decoding is completed, ‘m_final’ is the final decoded codeword, and the specific structure is as shown in Figure11.Figure 11
Decoding and postprocessing unit.


## 4.7. Pipeline Architecture

The preprocessing module, the initial syndrome generation module, the three-error traversal module, the two-error traversal module, the single-error traversal module, and the decoding and postprocessing module are connected step by step to form a 42-stage pipeline. The specific architecture is shown in Figure12.Figure 12
Pipeline architecture.


## 4.8. Hardware Implementation Results

The experiment and verification are divided into two parts, software verification and hardware verification. Software verification tests the performance of QR codes while hardware verification tests the acceleration effects of QR codes. Software verification part is carried out on the Personal Computer (PC), which is also mentioned in Section2. The verification software runs in VS2019, Intel core I5-6500, windows 10 environment, and the decoding time is shown in Table 8. In order to show the difference between various decoding algorithms, we have recorded the decoding error correction time of various decoding algorithms under different number of errors. There is no doubt that the more errors an encoded message has, the longer decoding time cost, and the unstable decoding delay will have an impact on the real-time performance of the IOT device. In addition, the software experiment content also included the average decoding time of various decoding algorithms by calculating average based on the probability distribution of the number of errors, the results can be used as a reference for the real-time performance of decoding algorithms.Table 8
Decoding time under various conditions.
EnvironmentWorksError numbers (us)Average 1Average 2123456PCDS in this paper1.122.164.2419.7648.36203.66190.003.863IFBM in [17]205.5142.7219.32955.93104.61182411065.57378.42ADA in [18]1.877117.41271.391269.36536.315954.55482.6649.97SSDDA in [19]1.70022.537822.863286.47482.94701.54681.2726.4Algorithm in [20]1134184826116822114173091529193.322089DS in [14]0.8545.6938.395.8198245240.269116.02Arria10Hardware implemented in this paper0.04610.04610.04610.04610.04610.04610.04610.0461Note that the average decoding time 1 is calculated by supposing all error patterns have the same probability of occurrence. And the average decoding time 2 is calculated by supposing there must be 1~5 errors in the received code and is under the environment of 7 dB SNR, where the occurring probability is 41.27% of one error, 36.49% of two errors, 15.92% of three errors, 5.03% of four errors, 1.1% of five errors, and 0.2% of six errors.The hardware verification framework is shown in Figure13. Random messages and noise are generated by ROM lookup table. The sum of encoded message and noise will input into the decoding accelerator. The BER counter records the error rate by comparing the decoding result with the original message.Figure 13
Hardware experimental framework.The decoding accelerator is deployed in Intel Arria10 10AX115U4F45I1SG FPGA; the results is given in the Table9.Table 9
Results of accelerator.
AvailableResultALMs43.72 k12.7 kBlock RAM55.6 Mbit0.15 MbitMax clock freq.—260.42 MHzLatency—46.07 nsIn this decoding framework, all error patterns are evenly distributed into the pipeline, so the decoding time is fixed. A complete decoding requires 125 clocks, the traverse modules cost 12 clocks, 6 clocks to traverse all patterns, and 6 clocks repeated after shifting. Therefore, after 12 clocks of pipeline processing, a valid decoding result can be obtained. At the operation frequency of 260.42 M Hz, every 12 clock outputs can be equivalent to a decoding speed of 21.7 M Hz, the decoding time is 46.07 ns, and the decoding time required of each condition is shown in Table8. Compared with PC, hardware decoding acceleration can obtain 4121 times of decoding speed increase and can maintain a constant decoding time.


## 5. Conclusion

This article introduces the feasibility and advantages of QR code in power carrier technology based on the concept of UPIoT, and according to its shortcomings (decoding complexity and defects with long decoding time) proposed a solution. By improving the DS decoding algorithm, the error pattern is split according to the characteristics of the inductive combination of error patterns, the proposed Error Pattern Induction method has been simulated to prove that the performance is not lost and is better than RS code. This article also analyses the hardware feasibility of separating error pattern traversal and decoding operations and implements an FPGA-based hardware decoding architecture on this basis, on the Intel Arria10 10AX115U4F45I1SG FPGA platform, an equivalent decoding frequency of up to 21.7 MHz is realized, which is 4121 times the decoding speed of software. To our best knowledge, the hardware decoding architecture proposed in this paper is the first hardware implementation of (73, 37, 13) QR code decoding architecture.While providing a new implementation scheme for PLC error correction coding based on UPIoT, this architecture also shows that QR codes with longer codewords can also be quickly decoded by our hardware frame.



---

*Source: 6699555-2021-03-17.xml*