CN115280696A - Verifying data integrity in a receiver - Google Patents

Abstract

A method for verifying data integrity in a receiver in a wireless communication network is disclosed. The method comprises the following steps: receiving (101) a data message, wherein the data message comprises a data element group and a checksum; computing (102) a complete syndrome vector based on the partial syndrome vectors, wherein the partial syndrome vectors are computed in parallel by multiplying portions of the parity check matrix with corresponding portions of the received data message; determining (103) that all vector elements of the complete syndrome vector are zero; and verifying (104) that the received data message is correct (104 a) when all vector elements of the complete syndrome vector are zero, and incorrect (104 b) otherwise. Corresponding computer program product, device and receiver are also disclosed.

Description

Verify data integrity in receiver

technical field

The present disclosure relates generally to the field of data integrity. It relates more particularly to verifying data integrity in receivers in wireless communication networks.

Background technique

To verify data integrity in a receiver, a cyclic redundancy check (CRC) is often used to detect errors in messages transmitted over potentially unreliable channels, such as radio channels, in wireless communication networks.

CRCs are often implemented in dedicated hardware, but can also be implemented in software on the processor.

A drawback of a hardware and/or software implemented CRC is that the amount of processing increases with message length and renders processing inefficient in terms of processing time and incurred overhead.

Therefore, alternatives for verifying data integrity in the receiver are needed.

Contents of the invention

It should be emphasized that the term "comprising/comprising", when used in this specification, is used to designate the presence of stated features, integers, steps or components, but does not exclude one or more other features, integers, steps, components or The presence or addition of groups. As used herein, the singular forms "a", "an", and "the" are intended to include the plural forms as well, unless the context clearly dictates otherwise.

In general, when an arrangement is referred to herein, the arrangement is to be understood as a physical article; for example, a device. A physical product may include one or more parts, such as control circuitry in the form of one or more controllers, one or more processors, and the like.

It is an object of some embodiments to address or mitigate, alleviate, or eliminate at least some of the above or other disadvantages.

According to a first aspect, this is achieved by a method for verifying data integrity in a receiver in a wireless communication network.

The method includes: receiving a data message, wherein the data message includes a set of data elements and a checksum; and calculating a complete syndrome vector based on a partial syndrome vector, wherein, by combining a portion of a parity check matrix with the received data message Multiplies the corresponding parts of , to compute partial syndrome vectors in parallel.

The method further includes: determining that all vector elements of the full syndrome vector are zero; and verifying that the received data message is correct when all vector elements of the full syndrome vector are zero and incorrect otherwise.

In some embodiments, the method further comprises: partitioning the parity-check matrix into column groups, and associating each column group with a corresponding portion of the data message; by multiplying each column group with its corresponding portion of the data message to calculate the partial syndrome vectors in parallel; and sum the calculated partial syndrome vectors to obtain the complete syndrome vector.

In some embodiments, the method further comprises: partitioning the parity-check matrix into non-overlapping matrix element groups, and associating each non-overlapping matrix element group with a corresponding portion of the data message; calculating the partial syndrome vectors in parallel by multiplying the group with its corresponding portion of the data message; and summing the calculated partial syndrome vectors to obtain the full syndrome vector.

In some embodiments, the method further comprises: partitioning the parity-check matrix into non-overlapping matrix element groups from column groups, and associating each non-overlapping matrix element group with a corresponding portion of the data message; multiplying each non-overlapping matrix element group of the group with its corresponding portion of the data message to compute partial syndrome vectors in parallel; and summing the computed partial syndrome vectors to obtain a full syndrome vector.

In some embodiments, the parity check matrix is associated with a checksum polynomial from which the parity check matrix is computed.

In some embodiments, the checksum is based on a group of data elements and is appended to the group of data elements in the data message to form a codeword.

In some embodiments, the received data message has already been computed by the transmitter and transmitted to the receiver.

In some embodiments, the checksum is one or more of: a cyclic redundancy check (CRC) and a block code checksum.

In some embodiments, a full syndrome vector comprising all zero vector elements indicates a matching checksum and/or error-free set of data elements.

In some embodiments, the parity check matrix is pre-computed and stored in a memory of the receiver and/or in a remote memory accessible to the receiver.

In some embodiments, the parity check matrix is a binary matrix.

In some embodiments, the parity check matrix includes rows that are shifted versions of each other.

In some embodiments, given a portion of a data message, the corresponding partial syndrome is computed by first reading a pre-computed portion of the parity check matrix from memory and initializing the partial syndrome vector.

In some embodiments, the bits of the portion of the data message are accessed one by one, and when a one is encountered, a first set of bits of the parity check matrix is added to the partial syndrome vector.

In some embodiments, the bits of a portion of a data message are accessed one by one, and when a zero is encountered, the partial syndrome vector is left unchanged.

In some embodiments wherein each accessed column in the parity-check matrix is a shifted version of the previous column, wherein when each bit of the portion of the data message and the portion of the parity-check matrix has been accessed, Just shift in a new bit.

In some embodiments, one or more software threads of execution and/or processing elements are assigned to one or more portions of a parity check matrix and corresponding portions of a data message to compute partial syndrome vectors in parallel.

A second aspect is a computer program product comprising a non-transitory computer readable medium having thereon a computer program comprising program instructions. The computer program is loadable into the data processing unit and is configured to cause performance of the method according to the first aspect when the computer program is run by the data processing unit.

A third aspect is an apparatus for verifying data integrity in a receiver in a wireless communication network.

The device includes a controller configured to cause: receiving a data message, wherein the data message includes a set of data elements and a checksum; and computing a full syndrome vector based on the partial syndrome vector, wherein the parity Partial syndrome vectors are computed in parallel by multiplying parts of the syndrome matrix with corresponding parts of the received data message.

The controller is further configured to cause: determining that all vector elements of the full syndrome vector are zero; and verifying that the received data message is correct when all vector elements of the full syndrome vector are zero and incorrect otherwise of.

In some embodiments, the controller is further configured to cause: partitioning the parity-check matrix into column groups and associating each column group with a corresponding portion of the data message; by associating each column group with its corresponding portion of the data message calculating the partial syndrome vectors in parallel by multiplying the parts; and summing the calculated partial syndrome vectors to obtain the complete syndrome vector.

In some embodiments, the controller is further configured to cause: partitioning the parity-check matrix into non-overlapping groups of matrix elements and associating each non-overlapping group of matrix elements with a corresponding portion of the data message; multiplying sets of overlapping matrix elements with corresponding parts of their data messages to compute partial syndrome vectors in parallel; and summing the computed partial syndrome vectors to obtain a complete syndrome vector.

In some embodiments, the controller is further configured to cause: partitioning the parity-check matrix into non-overlapping groups of matrix elements from column groups, and associating each non-overlapping group of matrix elements with a corresponding portion of the data message; by computing partial syndrome vectors in parallel by multiplying each non-overlapping matrix element group from the column group with its corresponding portion of the data message; and summing the computed partial syndrome vectors to obtain the full syndrome vector.

In some embodiments, the parity check matrix is associated with a checksum polynomial from which the parity check matrix is computed.

In some embodiments, the checksum is based on a group of data elements and is appended to the group of data elements in the data message to form a codeword.

In some embodiments, the received data message has already been computed by the transmitter and transmitted to the receiver.

In some embodiments, the checksum is one or more of: a cyclic redundancy check (CRC) and a block code checksum.

In some embodiments, a full syndrome vector comprising all zero vector elements indicates a matching checksum and/or error-free set of data elements.

In some embodiments, the parity check matrix is pre-computed and stored in a memory of the receiver and/or in a remote memory accessible to the receiver.

In some embodiments, the parity check matrix is a binary matrix.

In some embodiments, the parity check matrix includes rows that are shifted versions of each other.

In some embodiments, the controller is further configured to cause: given a portion of a data message, to compute a corresponding partial check by reading a precomputed portion of a parity check matrix from memory and initializing a partial syndrome vector son.

In some embodiments, the controller is further configured to cause the bits of the portion of the data message to be accessed one by one, and when a one is encountered, to add the first set of bits of the parity check matrix to the partial syndrome vector.

In some embodiments, the controller is further configured to cause the bits of the portion of the data message to be accessed one by one, and when a zero is encountered, to leave the partial syndrome vector unchanged.

In some embodiments, the controller is further configured to cause a row of the parity check matrix to be shifted when each bit of the portion of the data message has been accessed.

In some embodiments, one or more software threads of execution and/or processing elements are assigned to one or more portions of a parity check matrix and corresponding portions of a data message to compute partial syndrome vectors in parallel.

In some embodiments, a device is operatively connectable to general-purpose hardware having one or more parallel processing elements configured to process parallelized computations.

In some embodiments, each of the one or more parallel processing elements is configured to: compute in parallel the partial syndrome vectors by multiplying portions of the parity check matrix with corresponding portions of the data message Corresponding to one or more partial syndrome vectors.

In some embodiments, general-purpose hardware with one or more parallel processing elements is included in the receiver and/or in the cloud environment.

In some embodiments, the general-purpose hardware includes a graphics processing unit (GPU).

A fourth aspect is a receiver in a wireless communication network, the receiver comprising the device according to the third aspect.

In some embodiments, the receiver is configured to receive data and verify the integrity of the data.

Any of the above aspects may additionally have features identical to or corresponding to any of the various features as described above for any of the other aspects.

An advantage of some embodiments is that alternatives are provided for verifying data integrity in the receiver.

Another advantage of some embodiments is that parallelization of operations increases processing efficiency in terms of processing time and incurred overhead than is possible according to prior art approaches.

Yet another advantage of some embodiments is that parallelization of operations enables processing elements in hardware to process operations independently and in different timings from each other.

A further advantage of some embodiments is that parallelization of operations enables a more efficient implementation in terms of utilizing available resources in hardware than is possible according to prior art approaches.

It should be noted that even though embodiments are described herein in the context of verifying data integrity in a receiver, some embodiments may be equally applicable and/or beneficial in other contexts.

Description of drawings

Further objects, features and advantages will emerge from the following detailed description of embodiments with reference to the accompanying drawings. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating example embodiments.

Figure 1 is a flowchart illustrating example method steps according to some embodiments;

Figure 2a is a schematic block diagram illustrating example operations according to some embodiments;

Figure 2b is a schematic block diagram illustrating example operations according to some embodiments;

Figure 2c is a schematic block diagram illustrating example operations according to some embodiments;

Figure 3a is a schematic block diagram illustrating example operations according to some embodiments;

Figure 3b is a schematic diagram illustrating an example portion of a parity check matrix according to some embodiments;

Figure 3c is a schematic diagram illustrating an example portion of a data message and an example portion of a parity check matrix, according to some embodiments;

Figure 4 is a schematic block diagram illustrating an example device according to some embodiments; and

Figure 5 is a schematic diagram illustrating an example computer readable medium according to some embodiments.

Detailed ways

As already mentioned above, it should be emphasized that the term "comprising/comprising", when used in this specification, is used to designate the presence of stated features, integers, steps or components, but not to exclude one or more other features, integers , the presence or addition of a step, component, or group thereof. As used herein, the singular forms "a", "an", and "the" are intended to include the plural forms as well, unless the context clearly dictates otherwise.

Embodiments of the present disclosure will be more fully described and illustrated below with reference to the accompanying drawings. However, the solutions disclosed herein can be implemented in many different forms and should not be construed as limited to only the embodiments set forth herein.

As mentioned above, a drawback of hardware and/or software implemented CRCs is that the amount of processing increases with message length and renders processing inefficient in terms of processing time and incurred overhead.

In the following, embodiments will be presented in which alternatives for verifying data integrity in the receiver are described.

As described herein, general-purpose hardware typically includes hardware that includes one or more parallel processing elements configured to process parallelized operations, where the one or more processing elements further include Local data storage for these operations.

As described herein, operations generally include matrix and vector operations, where operations may include matrix multiplication and computation of matrix products, and vector operations may include summation of matrix products.

As described herein, the checksum typically includes a cyclic redundancy check (CRC) and/or a block code checksum.

The CRC is usually implemented using some sort of shift register technique, usually in a serial fashion. Data messages are processed in pieces while the shift register is being updated. Finally, the shift register state forms the checksum to be appended. In its most basic form, a data message is processed one bit at a time, but several consecutive bits, such as 8 or 32 bits, may also be processed together.

CRC computation can also be parallelized by splitting the data message into multiple subsequences and computing a temporary CRC for each subsequence. Then, a relatively complex linear function is applied to each temporary CRC, and the final CRC is obtained by adding the results using XOR addition.

Since the amount of processing increases with message length, the processing time is longer for long messages. This is especially true for software implementations. Therefore, this makes implementing CRC on general-purpose processors problematic.

Because parallelization is based on serial computation for each subsequence, in the end the complex function that needs to be performed for all subsequences adds an additional computational burden and is therefore difficult to compute efficiently on modern hardware including one or more processing elements CRC.

It should be noted that even though the embodiments are described herein in the context of verifying data integrity in a receiver in a wireless communication network, where the receiver is operatively connectable to one or more parallel servers with computations configured to process parallelization General-purpose hardware for processing elements, some embodiments may also be equally applicable and/or beneficial in other contexts where checksums are used to verify the data integrity of received messages.

It should also be noted that even though embodiments are described herein in the context of general-purpose hardware having one or more parallel processing elements configured to handle parallelized computations, some embodiments may also be implemented in each of the one or more processing elements It is also applicable and/or beneficial in other contexts where each processing element is configured to process a set of calculations serially.

Furthermore, it should be noted that even though embodiments are described herein in the context of summing computed partial syndrome vectors to obtain a complete syndrome vector, some embodiments may also be used in other contexts (wherein one or more parallel processing elements Two or more partial syndrome vectors of the calculated partial syndrome vectors computed in one parallel processing element of are also summed in the one parallel processing element, and wherein the summed two or It is equally applicable and/or beneficial in that more calculated partial syndrome vectors form a subset of those calculated partial syndrome vectors which are summed to obtain the full syndrome vector.

FIG. 1 is a flowchart illustrating method steps of an example method 100 according to some embodiments. Method 100 is used to verify data integrity in a receiver in a wireless communication network. Thus, method 100 may be performed, for example, by apparatus 400 and/or controller 410 of FIG. 4 ; all of which will be described later herein.

Method 100 includes the following steps.

In step 101 a data message is received, wherein the data message comprises a set of data elements and a checksum (cf. Figures 2a to 2c).

Alternatively or additionally, a group of data elements may comprise a sequence of data elements.

In some embodiments, the received data message has already been computed by the transmitter and transmitted to the receiver.

For example, a receiver receiving the message may be included in a mobile communication device and operate in a wireless communication network.

In some embodiments, the checksum is based on groups of data elements and is appended to the groups of data elements in the data message to form a codeword (cf. Fig. 2a).

In some embodiments, the checksum is one or more of: a cyclic redundancy check (CRC) and a block code checksum.

As mentioned above, checksums (eg, CRC) are often used to detect errors in messages transmitted over potentially unreliable channels, such as radio channels. For example, the 5G NR standard uses several different CRCs in the air interface; these are described in 3GPPTS 38.212 section 5.1.

As mentioned above, a CRC is a checksum, where the principle of a checksum is that for the transmitter, a sequence, the checksum, is calculated based on a group of data elements and appended to the group of data messages (refer to Figure 2a).

The receiver then performs the same calculation and checks (ie verifies) that the checksum matches, in which case the data message is declared error-free. If the checksums do not match, a non-matching checksum indicates that the data message contains errors and is typically discarded.

The receiver can mimic the transmitter by calculating a CRC based on the received data message, and then compare this CRC to the appended CRC sequence. Another way to check the CRC is to run the same CRC calculation algorithm on the entire data message (including the CRC). In this case, the calculated value should be zero.

CRC is a linear block code in which a transmitted data message including a checksum is treated as a codeword. In addition, CRC is usually applied to binary sequences, and thus becomes a binary linear block code. CRCs can also be used on data messages based on larger character tables.

The CRC is defined mathematically by long polynomial division. The divisor polynomial is based on the data message and the dividend is a fixed polynomial (CRC polynomial). The quotient is discarded, and the resulting CRC sequence is derived from the remainder.

In step 102, the full syndrome vector is computed based on the partial syndrome vectors, wherein the partial syndrome vectors are computed in parallel by multiplying parts of the parity check matrix with the corresponding parts of the received data message (cf. Fig. 3a to 3c).

In some embodiments, the parity check matrix is associated with a checksum polynomial (eg, a CRC polynomial) from which the parity check matrix is computed.

In some embodiments, the parity check matrix is a binary matrix.

In some embodiments, the parity check matrix includes rows that are shifted versions of each other.

Alternatively or additionally, this form of the parity check matrix (i.e. the rows are shifted versions of each other) requires only one row to be stored in memory, thus reducing the required memory size as well as the number of read operations .

In some embodiments wherein each accessed column in the parity-check matrix is a shifted version of the previous column, wherein when each bit of the portion of the data message and the portion of the parity-check matrix has been accessed, Just shift in a new bit.

Alternatively or additionally, the rows of the parity check matrix may be generated from a linear feedback shift register whose feedback polynomial is the same (or inverse) as the polynomial defining the CRC.

In some embodiments, the bits of the portion of the data message are accessed one by one, and when a one is encountered, a first set of bits of the parity check matrix is added to the partial syndrome vector.

In some embodiments, the bits of a portion of a data message are accessed one by one, and when a zero is encountered, the partial syndrome vector is left unchanged.

Alternatively or additionally, the full syndrome vector is calculated as the sum of the calculated partial syndrome vectors (cf. Figs. 3a to 3c).

Alternatively or additionally, the integrity syndrome vector indicates the data integrity of the received data message.

In some embodiments, a full syndrome vector comprising all zero vector elements indicates a matching checksum and/or error-free set of data elements.

In some embodiments, the parity check matrix is pre-computed and stored in a memory of the receiver and/or in a remote memory accessible to the receiver.

In some embodiments, given a portion of a data message, the corresponding partial syndrome is computed by first reading a pre-computed portion of the parity check matrix from memory and initializing the partial syndrome vector.

In some embodiments, one or more software threads of execution and/or processing elements are assigned to one or more portions of a parity check matrix and corresponding portions of a data message to compute partial syndrome vectors in parallel.

In optional step 102a-1, in some embodiments the parity check matrix is partitioned into column groups and each column group is associated with a corresponding part of the data message (cf. Figures 3a to 3c).

In optional step 102b-1, in some embodiments, partial syndrome vectors are computed in parallel by multiplying each column group with its corresponding part of the data message (cf. Figures 3a to 3c).

In optional step 102a-2, in some embodiments, the parity-check matrix is partitioned into non-overlapping groups of matrix elements, and each non-overlapping group of matrix elements is associated with a corresponding portion of the data message (see FIG. 3a to 3c).

Alternatively or additionally, groups of all-zero matrix elements may be discarded as their partial syndrome vectors will be zero and will not contribute to the sum (cf. step 102c).

In optional step 102b-2, in some embodiments, partial syndrome vectors are computed in parallel by multiplying each non-overlapping matrix element group with its corresponding part of the data message (cf. Figures 3a to 3c).

In optional step 102a-3, in some embodiments, the parity check matrix is partitioned into non-overlapping matrix element groups from column groups and each non-overlapping matrix element group is associated with a corresponding portion of the data message (Refer to Figures 3a to 3c).

Alternatively or additionally, groups of all-zero matrix elements may be discarded, since their partial syndrome vectors will be zero and will not contribute to the sum (cf. step 102c).

In optional step 102b-3, in some embodiments, partial syndrome vectors are computed in parallel by multiplying each non-overlapping matrix element group from the column group with its corresponding part of the data message (cf. 3c).

In optional step 102c, in some embodiments, the calculated partial syndrome vectors are summed to obtain a complete syndrome vector (see FIG. 3a ).

For example, by having each parallel processing element compute 10 partial syndrome vectors in succession, an implementation can compute 1000 partial syndrome vectors using only 100 parallel processing elements. Each parallel processing element may then compute the sum of its 10 partial syndrome vectors. Therefore, it can be considered that 100 partial syndrome vectors are calculated in parallel by 100 parallel processing elements, and each parallel processing element calculates its partial syndrome vector by iterating on some parts.

Alternatively or additionally, the full syndrome vector is obtained either by computing the sum of subsets of the partial syndrome vectors in one or more parallel processing elements and then summing the sums of the subsets, or by computing a Or the sum of the partial syndrome vectors calculated by multiple parallel processing elements to obtain the complete syndrome vector, and the sum of the partial syndrome vectors can be calculated.

In step 103, a first possibility is that all vector elements of the complete syndrome vector are determined to be zero, ie the complete syndrome vector is a zero vector ("Yes" path from step 103).

In step 103, a second possibility is that one or more vector elements of the vector elements of the complete syndrome vector are determined to be non-zero, i.e. the complete syndrome vector is a non-zero vector ("No from step 103 "path).

In step 104 (not shown), it is verified whether the received data message is correct or incorrect.

In step 104a, when all vector elements of the full syndrome vector are zero (ie, a zero vector), it is verified that the received data message is correct ("Yes" path from step 103).

In step 104b, when one or more of the vector elements of the full syndrome vector is non-zero (i.e., a non-zero vector), it is verified that the received data message is incorrect (“No” from step 103 path).

Any of the above-described steps of FIG. 1 may additionally have features that are the same as or correspond to any of the various features described below with respect to FIGS. 2 to 5 .

Figure 2a is a schematic block diagram illustrating example operations according to some embodiments. The operations of Figure 200a are performed in the transmitter, wherein the operations enable verification of data integrity in the receiver in the wireless communication network. Accordingly, the operations of diagram 200a may, for example, be configured to perform one or more of the method steps of FIG. 1 .

Figure 2a shows a data message including a checksum sequence (CRC (L bits)), the checksum sequence is based on the data element group, i.e., the data sequence (message (K bits)), is appended to further comprising the data elements Set of data messages.

Figure 2a further illustrates a CRC calculation, where a block-wise or bit-wise input of groups of data elements is provided and the calculated CRC is output and appended to the data message.

Figure 2b is a schematic block diagram illustrating example operations according to some embodiments. The operations of diagram 200b are used to verify data integrity in a receiver in a wireless communication network. Accordingly, the operations of diagram 200b may, for example, be configured to perform one or more of the method steps of FIG. 1 .

Figure 2b shows a received data message including CRC (N=K+L bits), where the CRC is calculated for verifying data integrity, and where a block-by-block or bit-by-bit input of the received data message including CRC is provided as input to the computation, and an output vector (L bits) to verify that the vector contains all zero vector elements.

Figure 2c is a schematic block diagram illustrating example operations according to some embodiments. The operations of diagram 200c are used to verify data integrity in a receiver in a wireless communication network. Accordingly, the operations of diagram 200c may, for example, be configured to perform one or more of the method steps of FIG. 1 .

Figure 2c shows a received data message (N bits) including a CRC and a checksum associated parity check matrix (L x N), where the received data message and checksum associated parity check matrix is given by Matrix-vector multiplication multiplies and outputs a vector (L bits) to verify that the vector includes all zero vector elements.

Figure 3a is a schematic block diagram illustrating example operations according to some embodiments. The operations of diagram 300a are used to verify data integrity in a receiver in a wireless communication network. Accordingly, the operations of diagram 300a may, for example, be configured to perform one or more of the method steps of FIG. 1 .

Figure 3a shows the computation of the full syndrome vector based on the partial syndrome vectors, where parts of the parity-check matrix are multiplied (MULT) by the corresponding parts of the received data message (i.e. parts of the received sequence) The partial syndrome vectors are calculated in parallel, and the calculated partial syndrome vectors are summed (SUM) to obtain the complete syndrome vector.

Figure 3a further shows: determining that all vector elements of the complete syndrome vector are zero (check whether it is zero), and verifying that the received data message is correct when all vector elements of the complete syndrome vector are zero , otherwise it is incorrect.

As described herein, matrix operations may be applied on matrices of any size limited only by the size of the local data store associated with one or more processing elements. In order to make processing more efficient and utilize one or more processing elements as high as possible, the matrix is split into several parts for processing.

当且仅当它满足矩阵方程

时是码字（指示CRC是正确的）。CRC是其中冗余位是所计算的CRC的二元线性块码的特例。因此，L是CRC的长度。Any binary linear block code can be defined by a parity check matrix (usually denoted H). H is an LxN binary matrix, where L is the number of redundant bits added, N is the length of the codeword, and K=NL is the length of the data message. A binary sequence of length N

iff it satisfies the matrix equation

is the codeword (indicating that the CRC is correct). A CRC is a special case of a binary linear block code where the redundant bits are the computed CRC. Therefore, L is the length of the CRC.

Parity check matrices are not unique: if A is a non-singular L×L matrix, then AH and H are parity check matrices for the same code.

并且校验它是全零来执行校验CRC。因为所有元素都是二元的，所以矩阵乘法可通过逻辑AND（即，二元乘法）和逻辑XOR（即，二元加法）来实现。这使软件实现和硬件实现都成为可能。Therefore, the syndrome vector of length L can be calculated by

And check it is all zeros to perform a check CRC. Since all elements are binary, matrix multiplication can be implemented by logical AND (ie, binary multiplication) and logical XOR (ie, binary addition). This enables both software and hardware implementations.

Computations can be parallelized in different ways, and items 1 to 3 below describe the different computations:

的不同部分，校验每个部分是零。这提供最多L路并行化。1. Parallel Computing

The different parts of , verify that each part is zero. This provides up to L-way parallelization.

分成M部分（M≤N）并且计算对应部分总和，然后将这些部分总和一起求和得到

。这提供最多N路并行化。求和可以在树中部分并行完成，在校验

之前，需要logM个最终步骤。每个部分可以是

的子序列，或者它可以是来自

的任意分段的元素集合。2. Convert the sequence

Divide into M parts (M≤N) and calculate the sum of the corresponding parts, and then sum the sums of these parts together to get

. This provides up to N-way parallelization. The summation can be done partially in parallel in the tree, after the check

Before, logM final steps are required. Each part can be

A subsequence of , or it can be a subsequence from

An arbitrary segmented collection of elements of .

3. The combination of item 1 and item 2 provides a maximum of L×N ways of parallelization.

Because L is usually a fixed small number (usually L≤32), and N can be on the order of several thousand, item 2 above can often provide sufficient parallelization by itself.

，使得每行是上面行向左移位一步。这意味着，对于长度为N的序列，它需要仅存储N+L-1个预先计算的奇偶校验位（或者，通过不存储第一行中L-1个起始零而仅存储N个所述奇偶校验位）。Then suppose the elements of H are

, such that each row is the row above shifted one step to the left. This means that, for a sequence of length N, it needs to store only N+L-1 precomputed parity bits (or, by not storing L-1 starting zeros in the first row, only N the parity bit).

可写为（模-2）总和

，其中

是H的第j列。给定这里的假设，会得到

。注意，这个总和的每一项或者是全零向量（当c_j=0时），或者是q序列的子序列（当c_j=1时）。syndrome vector

can be written as the (modulo-2) sum of

,in

is the jth column of H. Given the assumptions here, one gets

. Note that each term of this sum is either an all-zero vector (when _{cj =} 0), or a subsequence of the q-sequence (when _{cj =} 1).

，可通过首先从存储器中读取预先计算的奇偶校验序列

并且将

初始化成全零向量来计算对应的部分校验子

。然后，逐一访问位c_b、c_b+1等：当遇到“一”时，将奇偶校验序列的前L位添加到

；当遇到“零”时，

保持不变。在访问每一位之后，奇偶校验序列向左移位一步。given subsequence

, which can be obtained by first reading the precomputed parity sequence from memory

and will

Initialize to an all-zero vector to calculate the corresponding partial syndrome

. Then, access bits c _b , c _b+1 , etc. one by one: when a "one" is encountered, the first L bits of the parity sequence are added to

; when "zero" is encountered,

constant. After each bit is accessed, the parity sequence is shifted one step to the left.

的一个或几个子序列以计算出部分校验子总和。对于每个这样的子序列，可以使用上述方法。如果核被指配多个子序列，则它可以简单地在那些子序列上迭代，并且将部分校验子加起来。当这些核已经完成它们的计算时，它们的结果可以被加在一起而得到最终的总和，该总和是整体校验子。Given some processing elements, i.e. one or more cores, each core can be assigned

One or several subsequences of , to calculate the partial syndrome sum. For each such subsequence, the method described above can be used. If the core is assigned multiple subsequences, it can simply iterate over those subsequences and add up the partial syndromes. When the cores have completed their calculations, their results can be added together to get the final sum, which is the overall syndrome.

Figure 3b is a schematic diagram illustrating an example portion of a parity check matrix according to some embodiments.

Figure 3b shows a partitioned parity-check matrix comprising elements corresponding to its parts which can be multiplied with corresponding parts of a data message (eg a subset of data sequence elements).

Figure 3b further shows parts of the divided parity-check matrix, including one or more of the following: non-contiguous parts, parts across row and column subsets, non-rectangular parts, and parts with only zero elements (which can be skipped Pass).

Figure 3c is a schematic diagram illustrating an example portion of a data message and an example portion of a parity check matrix, according to some embodiments.

Fig. 3c shows a parity check matrix, wherein the parity check matrix is partitioned, and wherein the partitioned matrix parts correspond to parts of a data message, ie a subset of the data sequence comprising elements associated with the partitioned matrix parts.

Fig. 3c further shows a partial syndrome vector, i.e. a partial syndrome, wherein, by combining the divided matrix part with the corresponding part of the data message (i.e., a subset of the data sequence comprising elements associated with the divided matrix part ) to calculate the partial syndrome vector.

It should be noted that the calculation of the partial syndrome vectors is performed in parallel and may be performed by hardware (eg GPU) comprising one or more processing elements configured to perform the calculations in parallel.

Hardware comprising one or more processing elements is thus configured to minimize processing time, and by using one or more processing elements for parallel computations, these computations will be time-series independent.

Fig. 4 is a schematic block diagram illustrating an example device 400 according to some embodiments. The device 400 is used to verify data integrity in a receiver in a wireless communication network. Accordingly, device 400 and/or controller 410 may, for example, be configured to perform one or more of the method steps of FIG. 1 , and/or one or more of any of the steps otherwise described herein.

Apparatus 400 includes a controller 410 (eg, device control circuitry) configured to cause: receiving a data message, wherein the data message includes a set of data elements and a checksum; and computing a full syndrome based on the partial syndrome vector vector, wherein the partial syndrome vectors are computed in parallel by multiplying parts of the parity check matrix with corresponding parts of the received data message.

The controller 410 is further configured to cause: determining that all vector elements of the full syndrome vector are zero; and verifying that the received data message is correct when all vector elements of the full syndrome vector are zero, otherwise not correct.

As mentioned above, the device 400 includes a controller (CNTR; e.g., a control circuit or control module) 410, which in turn may include (or be otherwise associated; e.g., connected or connectable to) a receiver 401, e.g. The receiving circuit or receiving module, the receiver 401 is configured to receive a data message, wherein the data message includes a data element group and a checksum (compared with step 101 of FIG. 1 ).

The controller 410 further includes (or is otherwise associated with; e.g., connected or connectable to) a computer 402, such as a computing circuit or a computing module, configured to compute a complete syndrome vector based on the partial syndrome vector, wherein, Partial syndrome vectors are computed in parallel by multiplying parts of the parity check matrix with corresponding parts of the received data message (compare step 102 of FIG. 1 ).

The controller 410 further includes (or is otherwise associated with; e.g., connected or connectable to) a determiner 403, such as a determination circuit or a determination module, configured to determine that all vector elements of the complete syndrome vector are zero (compared with step 103 of Fig. 1).

Controller 410 further includes (or is otherwise associated with; e.g., connected or connectable to) verifiers 404a and 404b, such as verification circuits or verification modules, configured to verify received data messages when complete True when all vector elements of the subvector are zero (compare step 104a of FIG. 1 ), otherwise incorrect (compare step 104b of FIG. 1 ).

In some embodiments, the controller 410 further includes (or is otherwise associated with; for example, connected or connectable to): a divider 402a-1, such as a divider circuit or a divider module, the divider 402a-1 is configured to divide parity the parity check matrix is divided into column groups, and each column group is associated with a corresponding part of the data message (compare with step 102a-1 of FIG. 1); and a computer 402b-1, such as a computing circuit or computing module, computer 402b -1 is configured to compute partial syndrome vectors in parallel by multiplying each column group with its corresponding part of the data message (compared to step 102b-1 of FIG. 1 ).

In some embodiments, the controller 410 further includes (or is otherwise associated; eg, connected or connectable to): a divider 402a-2, such as a divider circuit or a divider module, configured to divide the parity partitioning the check matrix into non-overlapping groups of matrix elements and associating each non-overlapping group of matrix elements with a corresponding portion of the data message (compare step 102a-2 of FIG. 1 ); and a computer 402b-2, such as a computing circuit Or computation module, computer 402b-2 is configured to compute partial syndrome vectors in parallel by multiplying each non-overlapping matrix element group with its corresponding part of the data message (compare step 102b-2 of FIG. 1 ).

In some embodiments, the controller 410 further includes (or is otherwise associated; eg, connected or connectable to): a divider 402a-3, such as a divider circuit or a divider module, configured to divide the parity partitioning the check matrix into non-overlapping groups of matrix elements from groups of columns, and associating each non-overlapping group of matrix elements with a corresponding portion of the data message (compare step 102a-3 of FIG. 1); and computer 402b-3 , such as computing circuits or computing modules, the computer 402b-3 is configured to compute partial syndrome vectors in parallel by multiplying each non-overlapping matrix element group from the column group with its corresponding part of the data message (similar to the steps of FIG. 1 102b-3).

In some embodiments, the controller 410 further includes (or is otherwise associated with; e.g., connected or connectable to) a summer 402c, such as a summing circuit or a summing module, configured to combine the calculated The partial syndrome vectors are summed to obtain a complete syndrome vector (compared with step 102c in FIG. 1 ).

In some embodiments, the device is operatively connectable to general-purpose hardware having one or more parallel processing elements configured to process parallelized computations.

In some embodiments, each of the one or more parallel processing elements is configured to: compute in parallel the partial syndrome vectors by multiplying portions of the parity check matrix with corresponding portions of the data message Corresponding to one or more partial syndrome vectors.

In some embodiments, general-purpose hardware with one or more parallel processing elements is included in the receiver and/or in the cloud environment.

In some embodiments, the general-purpose hardware includes a graphics processing unit (GPU).

In some embodiments, the device 400 may further optionally include (or be otherwise associated with; for example, connected or connectable to) a transceiver TX/RX 420, such as a transceiver circuit or a transceiver module, the transceiver TX/RX 420 is Configured to transmit and receive radio signals, eg upon verification of data integrity in a receiver in a wireless communication network.

In general, when an arrangement is referred to herein, the arrangement is to be understood as a physical article; for example, a device. A physical product may include one or more parts, such as control circuitry in the form of one or more controllers, one or more processors, and the like.

The described embodiments and their equivalents may be implemented in software or hardware or a combination thereof. These embodiments may be implemented by general-purpose circuits. Examples of general-purpose circuits include: digital signal processors (DSPs), central processing units (CPUs), graphics processing units (GPUs), coprocessor units, field programmable gate arrays (FPGAs), and other programmable hardware. Alternatively or additionally, embodiments may be performed by a dedicated circuit, such as an Application Specific Integrated Circuit (ASIC). General purpose circuitry and/or special purpose circuitry may, for example, be associated with or included in a device such as a wireless communication device.

Embodiments may be found within an electronic device, such as a wireless communication device, comprising an arrangement, circuitry and/or logic according to any of the embodiments described herein. Alternatively or additionally, an electronic device, such as a wireless communication device, may be configured to perform a method according to any of the embodiments described herein.

According to some embodiments, a computer program product comprises a computer readable medium such as eg a Universal Serial Bus (USB) memory, a plug-in card, an embedded drive or a read only memory (ROM).

FIG. 5 shows an example computer readable medium in the form of a compact disc (CD) ROM 500 . A computer readable medium has stored thereon a computer program comprising program instructions. The computer program may be loaded into a data processor (PROC) 520 which may be included in the wireless communication device 510, for example. When loaded into a data processor, the computer program may be stored in a memory (MEM) 530 associated with or contained in the data processor.

In some embodiments, the computer program may, when loaded into and run by a data processing unit, cause the execution of one or more of the method steps according to, for example, FIG. 1 and/or any of the steps otherwise described herein .

In some embodiments, the computer program may, when loaded into and run by the data processing unit, cause one of the operations according to, for example, FIGS. 2a to 2c and/or FIG. 3a and/or any of the operations otherwise described herein or the execution of multiple operations.

Generally, all terms used herein are to be interpreted according to their ordinary meaning in the relevant technical field, unless a different meaning is clearly given and/or implied from the context in which the term is used.

Reference has been made herein to various embodiments. However, those skilled in the art will recognize many changes to the described embodiments which would still fall within the scope of the claims.

For example, method embodiments described herein disclose example methods with steps performed in a certain order. However, it is to be appreciated that these sequences of events may occur in another order without departing from the scope of the claims. Furthermore, even though some method steps have been described as being performed sequentially, they may also be performed in parallel. Thus, unless a step is explicitly described as being after or before another step and/or where it is implied that one step must be after or before another step, the steps of any method disclosed herein do not necessarily have to be preceded by another step. Execute in the exact order disclosed.

Also, it should be noted that in the description of the embodiments, the division of functional blocks into specific units is by no means intended to be limiting. Rather, these divisions are merely examples. A functional block described herein as one unit may be split into two or more units. Furthermore, functional blocks described herein as being implemented as two or more units may be combined into fewer (eg, a single) unit.

Wherever appropriate, any feature of any of the embodiments disclosed herein can be applied to any other embodiment. Likewise, any advantage of any of these embodiments may be applied to any other embodiment, and vice versa.

It is, therefore, to be understood that the details of the described embodiments are presented for illustrative purposes only and all changes which come within the scope of the claims are intended to be embraced therein.

Claims (25)

1. A method for verifying data integrity in a receiver in a wireless communication network, the method comprising the steps of: receiving (101) a data message, wherein the data message includes a set of data elements and a checksum, Computing (102) the full syndrome vector based on the partial syndrome vectors, wherein the partial syndrome vectors are computed in parallel by multiplying parts of the parity check matrix with corresponding parts of the received data message, determining (103) that all vector elements of said complete syndrome vector are zero, and Verifying (104) that said received data message is correct (104a) when all said vector elements of said full syndrome vector are zero, otherwise incorrect (104b). 2. The method of claim 1, further comprising the steps of: partitioning (102a-1) said parity-check matrix into column groups, and associating each column group with a corresponding portion of said data message, Computing (102b-1) partial syndrome vectors in parallel by multiplying each column group with its corresponding part of said data message, and The calculated partial syndrome vectors are summed (102c) to obtain a complete syndrome vector. 3. The method according to any one of claims 1-2, further comprising the steps of: dividing (102a-2) the parity-check matrix into non-overlapping groups of matrix elements and associating each non-overlapping group of matrix elements with a corresponding portion of the data message, Computing (102b-2) partial syndrome vectors in parallel by multiplying each non-overlapping matrix element group with its corresponding part of said data message, and The calculated partial syndrome vectors are summed (102c) to obtain a complete syndrome vector. 4. The method according to any one of claims 1-3, further comprising the steps of: partitioning (102a-3) the parity-check matrix into non-overlapping groups of matrix elements from groups of columns, and associating each non-overlapping group of matrix elements with a corresponding portion of the data message, computing (102b-3) partial syndrome vectors in parallel by multiplying each non-overlapping set of matrix elements from said set of columns with its corresponding portion of said data message, and The calculated partial syndrome vectors are summed (102c) to obtain a complete syndrome vector. 5. The method according to any one of claims 1-4, wherein the parity check matrix is associated with a checksum polynomial from which the parity check matrix is calculated. 6. The method according to any one of claims 1-5, wherein the checksum is based on the group of data elements and is appended to the group of data elements in the data message to form a code Character. 7. A method according to any of claims 1-6, wherein said received data message has been calculated by a transmitter and transmitted to said receiver. 8. The method according to any one of claims 1-7, wherein the checksum is one or more of the following: a cyclic redundancy check (CRC) and a block code checksum. 9. A method according to any of claims 1-8, wherein the complete syndrome vector comprising all zero vector elements indicates a matching checksum and/or error-free set of data elements. 10. The method according to any one of claims 1-9, wherein the parity-check matrix is pre-computed and stored in a memory of the receiver and/or in a in remote storage. 11. The method according to any one of claims 1-10, wherein the parity check matrix is a binary matrix. 12. The method of any of claims 1-11, wherein the parity check matrix comprises rows that are shifted versions of each other. 13. The method according to any one of claims 1-12, wherein, given the portion of the data message, by first reading a precomputed portion of the parity check matrix from memory and The partial syndrome vectors are initialized to calculate corresponding partial syndromes. 14. The method according to any one of claims 1-13, wherein the bits of the part of the data message are accessed one by one, and when a one is encountered, the bit of the parity check matrix A set is added to the partial syndrome vector. 15. The method according to any one of claims 1-14, wherein the bits of the portion of the data message are accessed one by one, and when a zero is encountered, the partial syndrome vector is kept at zero Change. 16. The method according to any one of claims 1-15, wherein each accessed column in the parity-check matrix is a shifted version of the previous column, wherein when the data has been accessed For each bit of the portion of the message and the portion of the parity check matrix, only one new bit is shifted in. 17. The method of any one of claims 1-16, wherein one or more software threads and/or processing elements for execution are assigned to one or more parts of the parity check matrix Computing the partial syndrome vectors in parallel with the corresponding part of the data message. 18. A computer program product comprising a non-transitory computer readable medium having thereon a computer program comprising program instructions, the computer program being loadable into a data processing unit and configured to : The computer program, when run by the data processing unit, results in the performance of the method according to any one of claims 1 to 17. 19. An apparatus for verifying data integrity in a receiver in a wireless communication network, the apparatus comprising a controller (410), the controller configured to cause: receiving a data message, wherein the data message includes a set of data elements and a checksum, Computing a full syndrome vector based on a partial syndrome vector, wherein the partial syndrome vectors are computed in parallel by multiplying parts of a parity check matrix with corresponding parts of a received data message, determining that all vector elements of the full syndrome vector are zero, and Verifying that said received data message is correct when all said vector elements of said full syndrome vector are zero, otherwise incorrect. 20. The device of claim 19, wherein the device is operatively connectable to general-purpose hardware having one or more parallel processing elements configured to process parallelized computations. 21. The apparatus according to any one of claims 19-20, wherein each of the one or more parallel processing elements is configured to: A corresponding one or more of the partial syndrome vectors is computed in parallel by multiplying with a corresponding portion of the data message. 22. The device according to any of claims 19-21, wherein said general-purpose hardware with one or more parallel processing elements is comprised in said receiver and/or in a cloud environment. 23. The device of any one of claims 19-22, wherein the general-purpose hardware comprises a graphics processing unit (GPU). 24. A receiver in a wireless communication network, the receiver comprising an apparatus according to any one of claims 19-23. 25. The receiver of claim 24, wherein the receiver is configured to receive data and verify the integrity of the data.

Images