Disclosure of Invention
In view of this, the embodiments of the present application provide a method, an apparatus, a terminal device, and a storage medium for constructing an LDPC code of a flash memory, which can effectively solve the problems of influencing the implementation efficiency of hardware, and complicating the design.
In a first aspect, an embodiment of the present application provides a method for constructing an LDPC code of a flash memory, including:
determining construction parameters of the LDPC code, wherein the construction parameters are used for constructing a mother matrix of the LDPC code;
constructing a prototype matrix of each submatrix, simplifying the structure of each submatrix, and obtaining each simplified submatrix;
combining the simplified sub-matrices to obtain a sub-code rate matrix of the mother matrix, and combining the sub-code rate matrices to obtain a mother code prototype matrix;
Cyclic shift values are given to the mother code prototype matrix in an arithmetic progression mode;
and detecting whether each sub-matrix in the mother code prototype matrix contains 4 rings or not under the current shift value, if so, re-executing the step of endowing the mother code prototype matrix with a cyclic shift value by an arithmetic array method, and if not, finishing construction.
In some embodiments, the determining construction parameters of the LDPC code, the construction parameters being used to construct a mother matrix of the LDPC code, comprises:
calculating a lifting factor according to hardware parameters of the target flash memory, and calculating the column number of a user data matrix according to the lifting factor;
And determining the highest code rate and the lowest code rate of the target flash memory, and calculating the row number of the mother matrix and the row number of each sub-matrix according to the column number of the user data matrix, the highest code rate and the lowest code rate.
In some embodiments, the submatrices include a user data matrix, a code rate compatible matrix, a full-1 matrix, a dense matrix, and one specific structure submatrix;
The constructing a prototype matrix of each sub-matrix and simplifying the structure of each sub-matrix comprises:
setting all the first row data of the user data matrix to 0, and setting all the diagonal data of the code rate compatible matrix to 0;
Setting the dense matrix as a full matrix, and setting the column weight of each submatrix as a value in a preset interval based on a preset column weight, wherein the column weight is the number of 1 in one column of data of the matrix.
In some embodiments, the resetting the column weight of each of the submatrices to a value within a preset interval based on a preset column weight further includes:
The maximum column weight of the mother matrix is not more than the preset column weight +1;
The maximum column weight of the user data matrix is not more than a preset column weight-1;
The maximum column weight of the code rate compatible matrix is not more than a preset column weight-1;
In some embodiments, combining each of the simplified submatrices to obtain a submatrix of the mother matrix includes:
Prototype matrix construction is carried out on each sub-matrix through a progressive edge algorithm, and each simplified sub-matrix is combined according to a preset position;
And determining the number of rows and columns to be deleted, continuously deleting the rows to be deleted from the second row, and continuously deleting the columns to be deleted from the second column of the code rate compatible matrix to obtain the subcode rate matrix of the mother matrix.
In some embodiments, the merging each of the subcode rate matrices to obtain a mother code prototype matrix includes:
and carrying out logical OR on the positions of each subcode rate matrix 1 and the cumulative or temporary matrix respectively to obtain a mother code prototype matrix.
In some embodiments, the assigning cyclic shift values to the mother code prototype matrix by means of an arithmetic progression includes;
selecting any prime number between 0 and the lifting factor as an equal difference value of each row of the mother code prototype matrix;
Setting initial values of each row for a first column of the mother code prototype matrix;
and generating a cyclic shift value of each row according to the initial value of each row and the equal difference value of each row.
In some embodiments, the hardware parameters include a firmware-filled length, a cyclic redundancy check length, a minimum page capacity, a maximum page capacity, a throughput rate, and an operating frequency;
Calculating a lifting factor according to the hardware parameters of the target flash memory, and calculating the number of columns of the user data field according to the lifting factor, wherein the method comprises the following steps:
calculating the maximum codeword length according to the maximum page capacity and the number of codewords;
calculating the size of a user data field of each codeword according to the firmware-padded length and the cyclic redundancy check;
Calculating a lifting factor according to the maximum codeword length, the throughput rate, the working frequency, the size of the user data field of each codeword and the hardware parameters of the target flash memory controller;
And calculating the column number of the user data field according to the lifting factor and the size of the user data field of each codeword.
In some embodiments, the determining the compatible highest code rate and the lowest code rate, and calculating the number of rows of the mother matrix and the number of rows of each sub-matrix according to the highest code rate and the lowest code rate includes:
calculating the number of rows of the mother matrix and the number of rows of each sub matrix according to a preset inequality;
the expression of the inequality is as follows;
;
;
Wherein, R is the lowest code rate, R1 is the highest code rate, K is the number of columns of the user data field, M is the number of rows of the mother matrix, and M1 is the number of rows of the sub-matrix corresponding to the highest code rate.
In a second aspect, the present application also provides an LDPC code construction apparatus for a flash memory, including:
The first construction module is used for determining construction parameters of the LDPC code, wherein the construction parameters are used for constructing a mother matrix of the LDPC code;
The second construction module is used for constructing prototype matrixes of all the submatrices, simplifying the structures of all the submatrices and obtaining all the simplified submatrices;
the merging module is used for merging the simplified submatrices to obtain a submatrices of the mother matrix, and merging the submatrices to obtain a mother code prototype matrix;
The assignment module is used for assigning a cyclic shift value to the mother code prototype matrix in an arithmetic array mode;
And the detection module is used for detecting whether each sub-matrix in the mother code prototype matrix contains 4 rings or not under the current shift value, if so, executing the step of endowing the mother code prototype matrix with a cyclic shift value by an arithmetic array method again, and if not, finishing construction.
In a third aspect, the present application also provides a terminal device, the terminal device including a processor and a memory, the memory storing a computer program, the processor being configured to execute the computer program to implement the method for constructing an LDPC code of the flash memory.
In a fourth aspect, the present application also provides a computer readable storage medium storing a computer program which, when executed on a processor, implements the method for constructing an LDPC code of a flash memory.
The embodiment of the application has the following beneficial effects:
The LDPC code construction method of the flash memory of the application can reduce the shift calculation amount in the subsequent error correction application by simplifying the structure of each sub-matrix, simplify the design structure, endow the prototype matrix with the cyclic shift value by an arithmetic array method, reduce the random shift to be fixed shift, simplify the hardware realization complexity, simplify the storage cost of the cyclic shift value, and ensure that the finally generated LDPC code does not contain 4 rings by detecting the shift value, thereby ensuring the error correction performance of the LDPC code.
Detailed Description
The following description of the embodiments of the present application will be made clearly and completely with reference to the accompanying drawings, in which it is apparent that the embodiments described are only some embodiments of the present application, but not all embodiments.
The components of the embodiments of the present application generally described and illustrated in the figures herein may be arranged and designed in a wide variety of different configurations. Thus, the following detailed description of the embodiments of the application, as presented in the figures, is not intended to limit the scope of the application, as claimed, but is merely representative of selected embodiments of the application. All other embodiments, which can be made by a person skilled in the art without making any inventive effort, are intended to be within the scope of the present application.
The terms "comprises," "comprising," "including," or any other variation thereof, are intended to cover a specific feature, number, step, operation, element, component, or combination of the foregoing, which may be used in various embodiments of the present application, and are not intended to first exclude the presence of or increase the likelihood of one or more other features, numbers, steps, operations, elements, components, or combinations of the foregoing. Furthermore, the terms "first," "second," "third," and the like are used merely to distinguish between descriptions and should not be construed as indicating or implying relative importance.
Unless otherwise defined, all terms (including technical and scientific terms) used herein have the same meaning as commonly understood by one of ordinary skill in the art to which various embodiments of the application belong. The terms (such as those defined in commonly used dictionaries) will be interpreted as having a meaning that is the same as the context of the relevant art and will not be interpreted in an idealized or overly formal sense unless expressly so defined herein in connection with the various embodiments of the application.
The application provides a construction method of the LDPC code of a flash memory, which is characterized in that the construction method is characterized in that each sub-matrix is obtained by simplifying operation after the sub-matrix is constructed, then each sub-matrix is spliced to obtain a mother matrix, then corresponding checking operation is carried out, rings in the mother matrix are removed, and finally the needed QC-LDPC code matrix is obtained.
The LDPC code construction method of the flash memory is described below in connection with some specific embodiments.
Fig. 1 shows a flowchart of an LDPC code construction method of a flash memory according to an embodiment of the present application. Exemplary, the LDPC code construction method of the flash memory includes the steps of:
Step S100, determining construction parameters of the LDPC code, wherein the construction parameters are used for constructing a mother matrix of the LDPC code.
The LDPC code is a QC-LDPC code matrix used for error correction and data protection in the flash memory. The LDPC code comprises a plurality of submatrices, the concrete form of which is shown in figure 2, and comprises A, B, C, D, E, F and seven parts G in total, wherein part A corresponds to a user data matrix, part B corresponds to a code rate compatible matrix, part C is a full '-1' matrix and corresponds to an expanded full 0 matrix, part D, F, G corresponds to a dense matrix, and part E corresponds to an expanded unit matrix.
The construction of the LDPC code is related to the flash memory in which the LDPC code works, the LDPC code needs to be designed according to hardware parameters of the flash memory, otherwise, the generated LDPC code cannot work normally in the flash memory.
For convenience of explanation, the hardware parameters of the target flash memory that are compatible with the QC-LDPC code are preset in this embodiment, where the hardware parameters include a minimum page capacity, a maximum page capacity, a throughput rate, and an operating frequency. For convenience of explanation and calculation, the exemplary data of each working parameter is given herein that the minimum page capacity is written as MLC 16384+1536 Bytes, corresponding to the highest code rate of the matrix, and the maximum page capacity is written as QLC 16384+2608 Bytes, corresponding to the lowest code rate of the matrix. The number of stored codewords T per logical page is 4. Design throughput rate Φ > =4G Bps, design operating frequency f is 500 MHz.
First a maximum codeword length L is calculated from said maximum page capacity. The specific calculation expression is L= (16384+2608)/T=4748 Bytes.
In the formula, T as a denominator is 4, and the above result is obtained.
And calculating the size of the user data field of each codeword according to the length of the firmware padding and the cyclic redundancy check.
The firmware fill length is a known value, preferably 12 in this embodiment, denoted OOB (Out-of-Band field), and the cyclic redundancy check is a known value, preferably 4 in this embodiment, denoted CRC (Cyclic Redundancy Check).
The size lu= (16384/T) +oob+crc=4748 Bytes of each codeword user data field.
And calculating a lifting factor according to the maximum codeword length and the size of the user data field of each codeword.
The lifting factor needs to satisfy the following inequality:
。
in the formula, i is the convergence iteration number, and in this embodiment, it is preferably 3. Then post-take calculations may be made:
。
to facilitate data transfer and conversion, Z is typically an integer power of 2, where the lifting factor Z is preferably 256.
And calculating the column number of the user data field according to the lifting factor and the size of the user data field of each codeword.
The calculation expression of the user field K is that k=ceil (Lu/Z), ceil represents an upper rounding, where k=ceil (4112/32) =129, i.e. the number of columns corresponding to the user field is 129 columns, and 16 Bytes needs to be filled in the tail of the user data during encoding to match the requirement of Z-size alignment of QC-LDPC codes.
Next, the number of mother matrix rows M and the number of sub-matrix rows M1 corresponding to the highest code rate need to be calculated, which has the following expression:
;
;
For example, the highest code rate R1= 0.9214 and R2= 0.8694 to be compatible, and the above expression can be carried out to calculate M=19 and M1 =11, thus obtaining the construction parameters of the LDPC code.
According to the above construction parameters, a mother matrix of the LDPC code shown in fig. 2, that is, a size of the maximum matrix, may be constructed, and at this time, each element in the mother matrix has no initial value, which may be a default value such as 0 or null.
In the figure, N is the number of columns of the mother matrix, and the number of columns is based on the number of columns of the child matrix, so that no calculation is performed separately, and after the mother matrix is constructed by the child matrix in the subsequent step, the number of columns N is the number of columns of the mother matrix after the construction is completed.
Step S200, a prototype matrix of each submatrix is constructed, and the structure of each submatrix is simplified.
Two of the all-1 and all-0 matrices do not require special processing and therefore primarily handle user data matrices, code rate compatible matrices, and dense matrices.
And setting the first row data of the user data matrix to 0, and setting the diagonal data of the code rate compatible matrix to 0. The complexity of the coding can be simplified, because the cyclic shift operation is not needed for all 0 rows, the cyclic shift operation of the first row is directly reduced, and the exclusive or calculation can be directly performed.
In order to ensure that the check bit part is reversible, the dense matrix G is set to be a full matrix, and the column weight of each submatrix is set to be a value in a preset interval based on a preset column weight.
From this, the mother matrix maximum column weight is determined to be g+1. In order to ensure the power consumption balance of hardware, the relative concentration of column weights is kept, the solution of the subsequent steps is convenient, the column weights of the matrix A and the matrix B are defined as g-1, and the column weight of the D+F part is defined as g.
The column weights refer to the number of 1 in the column data of the matrix, because the decoding operation is performed column by column, the size in the column determines the power consumption of the processor when the column is processed, and the column weights are distributed in the manner described above, so that the column weights of all the columns are in the range around the preset column weight g, the processor does not have larger power consumption fluctuation when processing, can work in a stable state, and is a friendly stable state for both the processor and a power supply. Thus, the construction of each sub-matrix is completed.
And step S300, merging the simplified submatrices to obtain a submatrices of the mother matrix, and merging the submatrices to obtain a mother code prototype matrix.
In order to ensure maximum local girth and reduce the number of rings in the prototype matrix as much as possible, the present embodiment may employ a gradient edge (Progressing Edge Growth, PEG) algorithm to construct the prototype matrix for each sub-matrix.
After the sub-matrices are spliced according to the construction shown in fig. 2, a prototype matrix is obtained, which meets the construction parameters in step S100.
If the current adaptation length of the size of the flash memory logical page is N-2 columns, the current N columns are larger than the size of the flash memory logical page, and 2 rows and 2 columns need to be deleted when the current adaptation length of the size of the flash memory logical page is equal to the size of the flash memory logical page.
Meanwhile, in order to ensure the maximum local girth, the number of rings in a prototype matrix is reduced as much as possible, the rings are required to be a structure in the matrix, 4 rings cannot exist in the QC-LDPC code matrix, and the rings consist of 1, so that rows and columns with 1 need to be deleted. The present embodiment will therefore perform row and column erasures based on the flash logical page size.
The ring is a closed loop formed by connecting variable nodes, check nodes and edges end to end, and the 4-ring is a ring with the edge length of 4. For QC-LDPC codes, 4 loops in the matrix can be eliminated after reasonable assignment.
For rows, there is necessarily no 1 because the first row has been set to all 0s, so when a row needs to be deleted, the first row does not have to be deleted, and thus deletion can be started from the second row. The first row may be the first check block by exclusive-or operation of the information blocks, and may be the first row of all sub-matrices.
When deleting a column, the column needs to be deleted from the second column of the code rate compatible matrix, and because each element in the code rate compatible matrix can be calculated through the first element, the subsequent element deletion has no influence as long as the first element is reserved, and the column can be deleted from the second column of the code rate compatible matrix.
Thus reflecting the entire mother matrix, such as flash memory grains with compatible page sizes 16384+2432 Bytes, corresponding to 18×147 sub-matrices, corresponding to the removal of row 2 and column 131 from the mother matrix, the final prototype matrix example is shown in fig. 4.
It should be noted that, the subcode rate matrix obtained by combining in the above manner, that is, a subcode rate matrix corresponding to one of the subcode rates supported by the device, by using the above manner, a corresponding subcode rate matrix can be obtained for each subcode rate, and in this embodiment, the subcode rate matrices are further combined together to obtain a mother code prototype matrix.
In this embodiment, each sub-code rate matrix is combined to be a mother code prototype matrix, which may be obtained by performing or logic on the position of 1 in the sub-code rate matrix and the position of 1 in the corresponding mother matrix, and traversing all the sub-matrices to be supported. The merging when the sub-matrix size is (M-1) x (N-1) is as shown in fig. 3, the cumulative or temporary matrix 1 is the matrix which is bit-pressed or before the sub-matrix (M-1) x (N-1), the cumulative or temporary matrix 2 is the matrix which is bit-pressed or after the sub-matrix (M-1) x (N-1), and when all the sub-matrices are bit-pressed or after the completion of the cumulative or temporary matrix is the mother code prototype matrix.
The cumulative or temporary matrix is a matrix which is 0 at the initial time, for example, 5 sub-code rate matrixes exist, then the five sub-code rate matrixes and the cumulative or temporary matrix are subjected to OR operation in sequence, and after 5 OR operations are finished, the final cumulative or temporary matrix is a mother code prototype matrix which is an LDPC matrix used for verification.
And step S400, cyclic shift values are assigned to the mother code prototype matrix in an arithmetic progression mode.
The arithmetic method is to assign an arithmetic value to each row of the mother code prototype matrix, set an initial value to the first column, and then calculate the value of each element in each row based on the difference and the initial value.
According to the 4-ring-free theory of QC-LDPC codes, the arithmetic difference values of each row are different. The differences may be preferentially selected from prime numbers within 0~Z as the equal differences.
Illustratively, in this embodiment, Z is 256, so for the first few rows, the requirement that the last active element be "0" requires that the initial value of the first column be obtained according to the row weight of the row. In this embodiment, the arithmetic differences of the 1 st line to the 19 th line are 0, 5, 7, 2, 3, 1, 23, 6, 10, 110, 214, 27, 167, 163, 149, 17, 223, 151, and 4 in this order. The initial values of the 1 st to 19 th rows of this embodiment are 0, 175, 150, 138, 246, 97, 206, 154, 106, 256, 126, 47, 61, 174, 197, 94, 62, 70, and 229 in this order.
In this way, the shift values to the respective positions in the matrix can be calculated.
And S500, detecting whether each sub-matrix in the mother code prototype matrix contains 4 rings or not under the current shift value, if so, re-executing the step of endowing the mother code prototype matrix with a cyclic shift value by an arithmetic array method, and if not, finishing construction.
After the calculation is completed, it is necessary to check whether each sub-matrix contains 4 rings, wherein 4 rings are 4 rings consisting of 1, and if not, the construction is ended, and if so, the above step S400 is required to be executed again until there is no 4 rings in each sub-matrix.
As shown in fig. 5, the decoding algorithm is an ideal sum product decoding algorithm, the size in the figure is the size of the submatrix, the abscissa is the original bit error rate, and the ordinate is the uncorrected bit error rate, which is the sum product performance analysis of different half-port codes of each submatrix under the additive gaussian noise channel after the 4-ring division. It can be seen that as the original bit error rate increases, the uncorrected bit error rate of each sub-matrix exhibits a convergence state, which can indicate that the uncorrected bit error rate of each sub-matrix is effectively controlled after 4-ring division.
The LDPC code construction method of the flash memory of the embodiment can reduce the shift calculation amount in the subsequent error correction application of the LDPC code by simplifying the structure of each submatrix, also simplifies the design structure, reduces random shift to fixed shift by applying a cyclic shift value to the prototype matrix by an arithmetic array method, simplifies the hardware realization complexity, simplifies the storage cost of the cyclic shift value, and only needs to store an initial value and a difference value. And then, through detecting the shift value, the LDPC code finally generated is ensured not to have a loop, so that the stability of constructing the LDPC code is improved, the construction process of the LDPC code finally constructed is simple, the stable power consumption can be ensured when the LDPC code is actually calculated and used, the calculation operation is reduced, the burden of hardware is reduced, and the working efficiency is further improved.
Fig. 6 shows an LDPC code construction apparatus of a flash memory according to an embodiment of the present application, including:
A first construction module 10, configured to determine construction parameters of an LDPC code, where the construction parameters are used to construct a mother matrix of the LDPC code;
a second construction module 20, configured to construct a prototype matrix of each sub-matrix, and simplify the structure of each sub-matrix, so as to obtain each simplified sub-matrix;
A merging module 30, configured to merge the simplified submatrices to obtain a submatrices of the mother matrix, and merge the submatrices to obtain a mother code prototype matrix;
An assignment module 40, configured to assign cyclic shift values to the mother code prototype matrix by means of an arithmetic progression;
and the detection module 50 is configured to detect whether each sub-matrix in the mother code prototype matrix contains 4 rings under the current shift value, if so, re-execute the step of applying a cyclic shift value to the mother code prototype matrix by using the arithmetic array method, and if not, finish the construction.
The application also provides a terminal device comprising a processor and a memory, wherein the memory stores a computer program, and the processor is used for executing the computer program to implement the LDPC code construction method of the flash memory.
The terminal device of the present embodiment may be an electronic device such as a computer, a mobile phone, or a tablet, in which a flash memory is loaded, and the LDPC code in the flash memory is constructed based on the LDPC code construction method of the foregoing embodiment.
The present application also provides a computer-readable storage medium storing a computer program which, when executed on a processor, implements the method of constructing an LDPC code of a flash memory.
It will be appreciated that the apparatus of this embodiment corresponds to the method of the above embodiment, and that the alternatives in the above embodiment are equally applicable to this embodiment, so that the description will not be repeated here.
The processor may be an integrated circuit chip with signal processing capabilities. The processor may be a general purpose processor including at least one of a central processing unit (Central Processing Unit, CPU), a graphics processor (Graphics Processing Unit, GPU) and a network processor (Network Processor, NP), a Digital Signal Processor (DSP), an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA) or other programmable logic device, discrete gate or transistor logic device, discrete hardware components. A general purpose processor may be a microprocessor or the processor may be any conventional processor or the like that may implement or perform the methods, steps, and logic blocks disclosed in embodiments of the present application.
The Memory may be, but is not limited to, random access Memory (Random Access Memory, RAM), read Only Memory (ROM), programmable Read Only Memory (Programmable Read-Only Memory, PROM), erasable Read Only Memory (Erasable Programmable Read-Only Memory, EPROM), electrically erasable Read Only Memory (Electric Erasable Programmable Read-Only Memory, EEPROM), etc. The memory is used for storing a computer program, and the processor can correspondingly execute the computer program after receiving the execution instruction.
The computer readable storage medium of the present application stores the computer program used in the terminal device. For example, the computer readable storage medium may include, but is not limited to, U disk, removable hard disk, read-Only Memory (ROM), random access Memory (RAM, random Access Memory), magnetic or optical disk, etc. various media that can store program code.
In the several embodiments provided in the present application, it should be understood that the disclosed apparatus and method may be implemented in other manners. The apparatus embodiments described above are merely illustrative, for example, of the flow diagrams and block diagrams in the figures, which illustrate the architecture, functionality, and operation of possible implementations of apparatus, methods and computer program products according to various embodiments of the present application. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems which perform the specified functions or acts, or combinations of special purpose hardware and computer instructions.
In addition, functional modules or units in various embodiments of the application may be integrated together to form a single part, or the modules may exist alone, or two or more modules may be integrated to form a single part.
The functions, if implemented in the form of software functional modules and sold or used as a stand-alone product, may be stored in a computer-readable storage medium. Based on such understanding, the technical solution of the present application may be embodied essentially or in a part contributing to the prior art or in a part of the technical solution in the form of a software product stored in a storage medium, comprising several instructions for causing a computer device (which may be a smart phone, a personal computer, a server, a network device, etc.) to perform all or part of the steps of the method according to the embodiments of the present application.
The foregoing is merely illustrative of the present application, and the present application is not limited thereto, and any person skilled in the art will readily recognize that variations or substitutions are within the scope of the present application.