CN104160452A - Erasure correcting codes for storage arrays - Google Patents

Abstract

A data storage array includes m rows and n columns of entries, with each entry including at least one sector. In the array, mr+s locations are assigned to parity entries, such that each row has at least r parity entries. The parity entries correspond to a partial-maximum distance separable (PMDS) code that allows recovery from up to r erasures in each of the m rows as well as s additional erasures in any locations in the data array, where s is an integer greater than zero. The write data and the associated parity entries are written to the set of storage devices.

Description

For the correcting and eleting codes of storage array

Technical field

Present invention relates in general to storage system, more specifically, relate to for the part ultimate range of storage array and can divide (PMDS) correcting and eleting codes (erasure correcting code).

Background technology

The data redundancy scheme of computer system utilization such as parity calculations protected for the loss of data on memory device.In Redundant Array of Independent Disks (RAID) (RAID) system, value data and relevant odd even numerical value are in strip distribution across disc driver.RAID system is usually used to protect institute's canned data in hard disk drive (HDD) array to avoid calamitous disk failure.Two kinds of common RAID schemes are the RAID 5 protecting for single calamitous disk failure and the RAID 6 protecting for dual calamitous disk failure.

Flash memory is can carry out electricity with large-scale piecemeal to wipe and the solid state, non-volatile memory type of reprogramming.As HDD, flash memory device is divided into medium the sector that is generally 512 bits.Flash memory device further gathers sector for the page, and wherein each page has eight sectors conventionally, thereby each page comprises 4,000 or 4k byte (KB).Each sector is protected by error correcting code (ECC), its to multiple mistake (typically, single-bit error, although as other possibility of byte error be also feasible) correct.Common selection is Bose-Chaudhuri-Hocquenghem (BCH) code, as the BCH code of 8 correction or 15 correction, although may there be many versions.As in HDD, the page in flash memory device may be subject to the impact of hard error (HE).When the error correcting capability of this for example BCH code in the sector that has exceeded the page, occur.Compared with HDD, when the page is near it writes endurance life cycle ending, or in the time that its data are preserved near the ending of life cycle, the ability that exceeds BCH code in flash memory device becomes possibility more.Therefore, the quantity of the HE in flash memory device is estimated to increase in time, leaves potential HE on equipment.

The array being made up of flash memory device may run into calamitous equipment failure and mixed form that likely more ubiquitous HE combines.For example, use RAID 5 to protect institute's canned data in flash memory device may in the time there is potential HE, cause equipment failure.Therefore, for data-oriented band piece (for example, the data array that reads and/or write as unit), if an equipment in RAID 5 systems has experienced calamitous equipment failure, and some other equipment is subjected to HE, RAID 5 systems cannot be recovered the information in this data band piece.RAID 6 may allow data to be resumed, but RAID 6 requires ad hoc whole the second equipment for parity, and this is expensive in the time that major failure is HE.

Summary of the invention

Embodiment comprises method, system and the computer program for store data at storage array.Reception is write data and is arranged in the array that comprises the capable and n row entry of m, and wherein each entry comprises at least one sector.In this array, mr+s position is assigned to odd even entry, and makes every a line have at least r odd even entry.This odd even entry can be divided (PMDS) code corresponding to part ultimate range, its allow nearly to wipe for r time in the every a line from m is capable and data array in additionally the wiping and recover for s time of optional position, wherein s is greater than zero integer.The odd even entry of writing data and be associated is written to the set of memory device.

Other embodiment comprises a kind of method and computer program product for wiping of storage array corrected.Band piece is read in multiple receptions from n memory device.This is read band piece and comprises that capable with m of n is listed as the entry array of arranging, wherein each is listed as corresponding to one in memory device.This entry comprises data entry and mr+s odd even entry.Every a line comprises according to part ultimate range can divide (PMDS) code and at least r odd even entry generating from data entry.Determine that this reads band piece and comprise that at least one is wiped free of entry, mr+s are wiped free of entry at most, and do not have a line to have more than r+s to be wiped free of entry.Be wiped free of entry and be never wiped free of entry and be reconstructed, this produced be resumed read band piece.

Other Characteristics and advantages is achieved by technology of the present invention.Other embodiments of the invention and aspect have been described in detail and are considered to a part for claimed invention here.In order to utilize better this advantage and feature to understand the present invention, to describing and in addition reference of accompanying drawing.

Brief description of the drawings

Only by example, (multiple) of the present invention embodiment is described referring now to accompanying drawing, wherein:

Fig. 1 illustrate according to embodiment for providing part ultimate range can divide (PMDS) block diagram of system of code;

Fig. 2 illustrates the storage system according to embodiment;

Fig. 3 illustrates the content according to the encoding block of embodiment;

Fig. 4 entangles the treatment scheme of deleting according to embodiment for carrying out;

Fig. 5 is the treatment scheme for encoding to writing band piece according to embodiment; And

Fig. 6 is the treatment scheme for decoding to reading band piece according to embodiment.

Embodiment

Embodiments of the invention are the new groups with the correcting and eleting codes of two-dimensional structure.These correcting and eleting codes are known as part ultimate range here can divide (PMDS) code.(the embodiment of PMDS code as described herein can tolerate, recover from it) bust and at least two other hard errors (HE), even in the time that this other HE and the data array of for example, processing as unit (, read data band piece, write data band piece) are arranged in mutually colleague.

As used herein, term " bust " refers to the fault such as the whole solid state hard disc (SSD) of flash memory device.As used herein, term " entangles and delete " mistake referring to its location aware to be corrected.Entangle to delete and be different from " error correction ", as used herein, it is not that known mistake is corrected that the latter refers to its position.Correct and delete and the redundancy that approximately needs half quantity compared with error correction.As used herein, term " hard error " or " HE " refer to deletion (wiping) (, having the mistake of known location).

Although the error correcting code (ECC) such as Bose-Chaudhuri-Hocquenghem (BCH) code contributes to, after verification, the original bit error rate in flash memory device is reduced to reduced levels, final level still may be higher than the original bit error rate of the target of storage system.For example, 15 correction BCH code may be reduced to 2.7e by the original bit error rate of .001 after being decoded in the sector of 512 bytes (B) ^-9the original bit error rate.But, representing that this original bit error rate of the HE probability in flash memory device is substantially higher than the original bit error rate of typical hard drive, the latter's scope may be from 8e ^-14to 8e ^-16.Higher error rate may occur and occur near the ending of data preservation life cycle near the ending of writing endurance in flash memory device.

In the time having exceeded the error correcting capability of ECC, this situation will be detected with very high probability.For example, if implemented the BCH code of 15 correction, and the mistake more than 15 has occurred, BCH code self may detect such situation very much.Under any circumstance, conventionally increase taking cyclic redundancy check (CRC) (CRC) to guarantee that the probability of correcting is as 1e by mistake ^-26deng magnitude.Cannot detect that BCH code that mistake is corrected is equal to HDD and abandons and write or offset track writes in symptom.

Embodiment can adopt the multiple correction code of wiping arbitrarily known in the art.An example of the multiple erasure codes that embodiment adopts is Reed-Solomon (RS) code.RS code is known in the art and can be used to multiple wiping to correct.RS code is based on symbol, and wherein the size of symbol depends on application.For the instruction of the RS code about relating to RAID framework, referring to J.S.Plank " A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems ", Software, Practice & Experience, 995-1012, in September, 1997.

For given by Blaum-Roth 93 (BR93) code to multiple another efficient coding groups of correcting of wiping, as M.Blaum et al., New Array Codes for Multiple Phased Burst Correction "; IEEE Transactions on Information Theory; vol.39, pp.66-77 1993 is given.BR93 code is only to carry out XOR (XOR) computing to be tending towards the array code not as RS code complexity by avoiding Galois domain operation.

RS and BR93 code are all that ultimate range can be divided (MDS) coding, this means that they to delete and redundancy is carried out to optimal utilization in order to entangle.RS and BR93 code are the examples of two types in the embodiment as described herein repeatedly correcting and eleting codes that can utilize.Embodiment is not limited to this two kinds of codings because can also implement other coding group, such as general EVENODD code or general row to corner brace (RDC).

Contrary with the array of hard disk drive (HDD), the array of SSD presents the fault mode of mixing.On the one hand, just as the situation of HDD, exist calamitous SSD fault.On the other hand, exist hard error (HE), it is normally mourned in silence, because before attempting the sector that access comprises HE and do not know its existence.This situation makes the task of recovering in the framework of RAID (Redundant Array of Independent Disks (RAID)) type complicated.For example, suppose to have occurred calamitous SSD fault in RAID 5 frameworks.By carrying out distance (XOR) in the corresponding sector in each survival equipment, each sector of faulty equipment is reconstructed and starts to recover.But if there is the row that is also subjected to HE, such row has two sectors of having broken down.RAID 5 cannot recover and loss of data will occur from such situation.

It is the framework that uses RAID 6 types for a kind of possible solution of above situation.Wherein two SSD are used to parity.RAID 6 frameworks allow two in recovery a line to wipe sector.But such solution may be wasted, because need other whole equipment to protect for HE.The embodiment of PMDS code as described herein provides a kind of and HE has been processed and need to be for ad hoc whole the 2nd SSD of parity and solution between RAID 5 and RAID 6 by allowing.

In order to process the hybird environment of this HE with bust, take in the mode of writing information in SSD.In SSD, the mode of writing information is very different from the mode of writing information in HDD.In SSD, first new writing comprises wipes multiple contiguous sectors and they is all rewritten.Therefore, the of short duration write operation (for example, often next sector) in SSD array is not here problem: carry out once new writing, in each SSD, the data band piece of for example M sector is wiped free of and is being rewritten subsequently at every turn.In this case, recalculate parity as the new part writing.As described herein, suppose that storage array is formed (quantity that wherein " n " is SSD) by " m × n " that repeat one by one individual band piece.The parity that each m × n band piece is a separate unit and each band piece will be calculated according to embodiment as described herein.In addition, each new writing comprises the band piece (according to specific SSD and the other factors applying, use, this quantity can be 1) that writes m × n quantity.The embodiment of PMDS code families as described herein allows bust and HE to be corrected simultaneously.

Fig. 1 has described the block diagram of the system 100 of protecting according to the use PMDS of an embodiment.As shown in Figure 1, host computer 102 communicates with the array control unit 104 in storage system 110.Storage system 110 is stored data (wherein n is greater than 1) in the storage array 108 being made up of n memory device: memory device 0 106a, memory device 1 106b, memory device 2 106c are to memory device n-1 106d.In one embodiment, parity bit for example, is stored in memory device 106 together together with host data (, being expressed as data bit).In one embodiment, the memory device 106 in storage array 108 is implemented by the SSD such as flash memory device.In one embodiment, this array is made up of five flash memory devices, and each equipment has the memory capacity of 32G byte (GB).As shown in Figure 1, array control unit 104 is parts of storage system 110; In another embodiment, array control unit 104 is parts of host computer 102.

Fig. 2 illustrates the storage system 110 according to Fig. 1 of an embodiment.Storage system 110 can comprise multiple other parts such as receiver, forwarder and clock as known to those skilled, for object clearly and they are not illustrated.As shown in Figure 2, array control unit 104 comprises scrambler 202 and demoder 204.Scrambler 202 during writing processing, be used to receive one or more write input data bit (for example, from host computer 102) and generate write band piece, it comprises data entry and odd even entry.Each entry comprises " b " individual bit and can be corresponding to one or more pages, one or more sector and/or one or more symbol.In one embodiment, write band piece and in storage array 108, write and stride across the multirow in storage array 108.Demoder 204 is used to read one or more data entries from storage array 108 during reading processing.When detect in entry one or more HE time, demoder reads the whole band piece that (multiple) HE wherein detected from storage array 108.Demoder 204 and scrambler 202 all Internet access are shared data (for example, be used for recognition coding device 202 apply to generate the data of the type of coding of writing band piece to writing band piece).Read band piece and comprise the parity bit of being removed to generate reading out data by demoder 204.Demoder 204 is included in the reconstructor 206 having used while having there is at least one data strip object read failure.Read failure for example occurs in the time exceeding the error correcting capability of inside ECC of entry.Conventionally, error entries position is known, and therefore errors present (for example, (multiple) are wiped free of bar destination locations) and read band piece and be sent to reconstructor 206, and the latter attempts to recover the entry being wiped free of.

Fig. 3 has described the content (this data array is also known as " band piece " here) of the data array of storing across multiple memory devices 106.This data array is used PMDS code to encode as a unit by scrambler 202.As used herein, term " encoding strip thereof piece " refers to the entry group that common formation is write band piece and encoded as unit by using PMDS code.As used herein, term " decoding band piece " refers to the entry group that common formation is read band piece and decoded as unit by using PMDS code.

Data array depicted in figure 3 comprises that capable with m of n is listed as the entry of arranging.The other subscript of each entry type represents position (the, " a of this entry in data array ₀₀" be the entry that 0 row 0 is listed as in data array).In one embodiment, a part for memory device is shown in each list.In the band piece of describing at Fig. 3, each entry represents to be stored in " b " the individual symbol in the memory cell in flash memory device.In reason described herein, suppose that each in b symbol is a bit, but in fact it may be obvious larger symbol.Suppose that ECC (for example, BCH) and/or CRC are used to detect the entry read failure having occurred and identify erasure location arbitrarily.Embodiment as described herein supposes that read failure is reported, and regardless of the method that is used for identifying such read failure.

In one embodiment, demoder 204 receives reads band piece, and this is read band piece and has experienced from the HE in one or more entries of the storage array 108 of encoding in the described mode of Fig. 3.In one embodiment, carry out from HE and recover by the reconstructor 206 that is arranged in demoder 204.

According to an embodiment, the every a line in array is protecting by r odd even entry any mode of recovering of wiping for r time in this row.In other words, every a line of this data array forms [n, n-r, r+1] MDS code.In addition, " s " individual extra overall parity bit is added into this array.This s extra parity bit can be placed in this data array with many different modes, but for simplified characterization, in this example, they are placed in last column.It is of overall importance means that these parity bits are on all impacts to some extent of all " mn " the individual entries in data array.For example, below show the example in 4 × 5 data array, in r=1 and s=2 and in the end a line, put into two extra overall parity bits." D " designation data entry and " P " instruction odd even entry.

With reference to above data array, suppose to have occurred bust (that is to say, fault has all occurred a permutation in data array), and in addition, any place in data array there is the nearly HE at two places.PMDS as described herein will correct these faults (be also known as and wipe here).This situation illustrates in following data array.In the data array in left side, two other HE in different rows, are there are.In the array on right side, in going together mutually, two other HE are there are." F " indication fault and " N " instruction non-fault.

A kind of method addressing this problem is to use MDS coding.In 4 × 5 data array example, always have 6 odd even entries.For example, thereby feasible is to have the upper MDS of enforcement of 20 entries (, the symbol) code of 6 odd even entries.Therefore, can implement [20,14,7] MDS code (as RS code).The existing problem of the method is its complexity.In one embodiment, this MDS code is [20,14,7] RS code.This example that wherein the line number m in data array is 4 is only to provide for purposes of illustration.In application, more typical m numerical value is 16 or 32, and this will cause 18 or 34 odd even entries.Although be feasible, it is complicated implementing such coding.In normal running, basis of coding expects to utilize its bottom RAID structure based on row, as the single parity bit in the situation of RAID 5.Extra parity bit is called relatively less occasionally.The embodiment of PMDS code as described herein meets and has the constraint of level code to the RAID structure of bottom is used.The example that adds two overall parity bits at RAID 5, PMDS code can be corrected reaching every row wiping once, and in addition two places in any place is wiped and corrected.Therefore, PMDS code can be corrected the indication fault described in above data array and any situation of non-fault.

as the embodiment of the defined PMDS code in 1 of giving a definition

fixedjustice 1.Making c is that the data array of m × n makes every a line be encoded as [n, n-r, r+1] MDS code, and s parity character is added in this array in addition.If reached every row wipes for r time except correcting, c can pair array in arbitrarily wiping for s time of place correct, c is (r, s) PMDS code.

In definition 1, defined coding c is two-dimensional encoded.Suppose that entry, to be read by level by the mode of row, makes this be encoded to [mn, m (n-r)-s] liner code.Hereinafter based on its parity matrix, the practical structures of coding is described, this matrix is (mr+s) × mn matrix.

Fig. 4 has described the treatment scheme of being implemented by scrambler 204 according to an embodiment.At frame 402, ECC and/or CRC detect that fault has occurred reading of entry.At frame 404, send request to read all entries in the band piece that comprises the entry that read failure occurs.At frame 406, read band piece and be sent to together reconstructor 206 together with (multiple) position (entry positions that, (multiple) are wiped free of) of (multiple) entry that read failure occurs.At frame 408, determine whether the quantity that is wiped free of entry positions of reading in band piece is greater than the ability of deleting of entangling of this scheme.For example, if implemented to recover once to wipe in every row the code that adds two overall parity bits, and frame 408 finds to have wiped whole row together with three additional entries, exceeded the ability of deleting of entangling of PMDS code.If determine that at frame 408 quantity that is wiped free of entry positions of reading in band piece is greater than the ability of PMDS scheme, carries out frame 414 error condition is back to demoder 204.If within frame 408 is determined the ability of the quantity that is wiped free of entry positions in PMDS scheme, carry out frame 410.At frame 410, carry out reconstruct with the embodiment of PMDS correcting and eleting codes as described herein and read band piece.At frame 412, reconstructor 206 is exported the recovered band piece of reading to demoder 204, it comprise recover (multiple) and read entry.

Fig. 5 and Fig. 6 have described to follow the scrambler of classical coding theory and have wiped (deletion) demoder.Wiping in decoding, coding is the special circumstances of decoding, and wipes to solve and relate to syndrome (syndrome) and calculate, and solves subsequently linear system, and this linear system has the equation quantity equating with the quantity of wiping occurring.This syndrome according to as following given parity matrix calculate, as long as and wipe in coding wipe checking feature within, this system all has solution all the time.

Fig. 5 is the treatment scheme for encoding to writing band piece according to an embodiment.In one embodiment, the treatment scheme that Fig. 5 describes is avoided the impact of r catastrophic error and " s " individual other mistake by the performed data array with protection m × n of scrambler 220.At frame 502, suppose to have " n " row (for example, flash memory device) and " m " OK.In addition, suppose before m-1 capable in before entry in n-r row and m capable before n-r-s entry comprise data entry (or data entries).All the other entries are for blank and will use PMDS code as described below to encode.At frame 504, use [n, n-r] MDS code to encode to front m-1 is capable.In one embodiment, the result of every a line is stored among rear n-r entry of corresponding row.At frame 506, by solving linear system and last column is encoded based on parity matrix as described below.In one embodiment, this result store is in last column of this data array in last n-r-s the entry of m-1 in capable.

The treatment scheme for decoding to writing band piece of an embodiment of foundation in Fig. 6.In one embodiment, the processing that Fig. 6 describes is carried out for the data array of m × n by demoder 204.At frame 602, suppose to exist all to there is nearly r+s _jinferior " t " row of wiping (wherein 1≤j≤t), wherein s _jsum equals s, and in remaining row, has nearly and wipe for r time.At frame 604, use one or more [n, n-r] MDS code to correct being up to the row of wiping for r time.At frame 606, solve linear system and to all thering is nearly r+s by computing syndrome and based on parity matrix as described below _jinferior " t " row of wiping is corrected.

Be below the description for the code structure of the embodiment of PMDS code, and to will be as the description of the general condition of wiping correction code of PMDS code.In addition for selected application, the specific embodiment of PMDS code is described.

code structure

As described above, each entry is made up of b bit.In one embodiment, suppose that each entry is in a ring.This ring is defined by b order polynomial f (x), the product of two elements in this ring (getting the polynomial expression that reaches b-1 as number of times) is that divided by the remainder of f (x), (if f (x) is irreducible, this ring becomes Galois territory GF (2 by the product of two elements ^b)).Making α is the root of the polynomial f (x) of this ring of definition.The index that is represented as the f (x) of e (f (x)) is the index of α, and minimum value l (0 < l), and make α ^l=1.If f (x) is original function (primitive), e (f (x))=2 ^b-1.

In application, very important special case is f (x)=1+x+ ... + x ^p-1, wherein p is prime number.In this case, e (f (x))=p and f (x) are irreducible.In fact, and if only if 2 be original function in GF (p) time, proves that f (x) is irreducible not difficult.Therefore, number of times reach p-2 with 1+x+ ... + x ^p-1for the polynomial expression of mould forms ring and does not conventionally form territory.This ring is used to build Blaum-Roth (BR) code, and as the embodiment here described in, suppose that f (x) is irreducible or f (x)=1+x+ ... + x ^p-1, wherein p is prime number.General structure is defined as follows.

structure 1.Consider the f (x) taking scale-of-two polynomial expression as mould, wherein f (x) is irreducible or f (x)=1+x+ ... + x ^p-1, wherein p is prime number.Make mn≤e (f (x)), wherein e (f (x)) represents the index of f (x).Make c (m, n, r, s; F (x)) be coding, its (mr+s) × mn parity matrix is:

Wherein H (n, r, i, j) is r × n matrix

Wherein every behavior previous row as given in equation (2) square matrix H (n, r, i, j) be used in the art build it and measured by the given coding of order, for building the code that can encode and decode by row by row, and for framework difference MDS code.

Example 1 subsequently illustrates structure 1.

example 1.Consider m=3 and n=5,,

$H\left(\mathrm{3,5,1,3}\right)=\left(\begin{array}{ccccccccccccccc}1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1\\ 1& \mathrm{\&alpha;}& {\mathrm{\&alpha;}}^2& {\mathrm{\&alpha;}}^3& {\mathrm{\&alpha;}}^4& {\mathrm{\&alpha;}}^5& {\mathrm{\&alpha;}}^6& {\mathrm{\&alpha;}}^7& {\mathrm{\&alpha;}}^8& {\mathrm{\&alpha;}}^9& {\mathrm{\&alpha;}}^{10}& {\mathrm{\&alpha;}}^{11}& {\mathrm{\&alpha;}}^{12}& {\mathrm{\&alpha;}}^{13}& {\mathrm{\&alpha;}}^{14}\\ 1& {\mathrm{\&alpha;}}^2& {\mathrm{\&alpha;}}^4& {\mathrm{\&alpha;}}^6& {\mathrm{\&alpha;}}^8& {\mathrm{\&alpha;}}^{10}& {\mathrm{\&alpha;}}^{12}& {\mathrm{\&alpha;}}^{14}& {\mathrm{\&alpha;}}^{16}& {\mathrm{\&alpha;}}^{18}& {\mathrm{\&alpha;}}^{20}& {\mathrm{\&alpha;}}^{22}& {\mathrm{\&alpha;}}^{24}& {\mathrm{\&alpha;}}^{26}& {\mathrm{\&alpha;}}^{28}\\ 1& {\mathrm{\&alpha;}}^4& {\mathrm{\&alpha;}}^8& {\mathrm{\&alpha;}}^{12}& {\mathrm{\&alpha;}}^{16}& {\mathrm{\&alpha;}}^{20}& {\mathrm{\&alpha;}}^{24}& {\mathrm{\&alpha;}}^{28}& {\mathrm{\&alpha;}}^{32}& {\mathrm{\&alpha;}}^{36}& {\mathrm{\&alpha;}}^{40}& {\mathrm{\&alpha;}}^{44}& {\mathrm{\&alpha;}}^{48}& {\mathrm{\&alpha;}}^{52}& {\mathrm{\&alpha;}}^{56}\end{array}\right)$

$H\left(\mathrm{3,5,2,2}\right)=\left(\begin{array}{ccccccccccccccc}1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& \mathrm{\&alpha;}& {\mathrm{\&alpha;}}^2& {\mathrm{\&alpha;}}^3& {\mathrm{\&alpha;}}^4& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& {\mathrm{\&alpha;}}^5& {\mathrm{\&alpha;}}^6& {\mathrm{\&alpha;}}^7& {\mathrm{\&alpha;}}^8& {\mathrm{\&alpha;}}^9& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& {\mathrm{\&alpha;}}^{10}& {\mathrm{\&alpha;}}^{11}& {\mathrm{\&alpha;}}^{12}& {\mathrm{\&alpha;}}^{13}& {\mathrm{\&alpha;}}^{14}\\ 1& {\mathrm{\&alpha;}}^2& {\mathrm{\&alpha;}}^4& {\mathrm{\&alpha;}}^6& {\mathrm{\&alpha;}}^8& {\mathrm{\&alpha;}}^{10}& {\mathrm{\&alpha;}}^{12}& {\mathrm{\&alpha;}}^{14}& {\mathrm{\&alpha;}}^{16}& {\mathrm{\&alpha;}}^{18}& {\mathrm{\&alpha;}}^{20}& {\mathrm{\&alpha;}}^{22}& {\mathrm{\&alpha;}}^{24}& {\mathrm{\&alpha;}}^{26}& {\mathrm{\&alpha;}}^{28}\\ 1& {\mathrm{\&alpha;}}^4& {\mathrm{\&alpha;}}^8& {\mathrm{\&alpha;}}^{12}& {\mathrm{\&alpha;}}^{16}& {\mathrm{\&alpha;}}^{20}& {\mathrm{\&alpha;}}^{24}& {\mathrm{\&alpha;}}^{28}& {\mathrm{\&alpha;}}^{32}& {\mathrm{\&alpha;}}^{36}& {\mathrm{\&alpha;}}^{40}& {\mathrm{\&alpha;}}^{44}& {\mathrm{\&alpha;}}^{48}& {\mathrm{\&alpha;}}^{52}& {\mathrm{\&alpha;}}^{56}\end{array}\right)$

Structure 1 provides PMDS code for the polynomial function (, f (x)) in special parameter and definition ring or territory.The entry receiving by represented, the entry wherein wiped equals 0.The first step is to calculate the syndrome of rm+s.For c (m, n, r, s; F (x)) coding, use (1) given parity check matrix H (m, n, r, s; F (x)), this syndrome is:

$S_{\mathrm{ir}}=\underset{j=0}{\overset{n-1}{\&CirclePlus;}}{\mathrm{\&alpha;}}_{i,j}\mathrm{for}0\&le;i\&le;m-1---\left(3\right)$

$S_{\mathrm{ir}+i+1}=\underset{j=0}{\overset{n-1}{\&CirclePlus;}}{\mathrm{\&alpha;}}^{(\mathrm{ni}+j)2^l}{\mathrm{\&alpha;}}_{i,j}\mathrm{for}0\&le;i\&le;m-\mathrm{1,0}\&le;l\&le;r-2---\left(4\right)$

$S_{\mathrm{mr}+u}=\underset{i=0}{\overset{m-1}{\&CirclePlus;}}\underset{j=0}{\overset{n-1}{\&CirclePlus;}}{\mathrm{\&alpha;}}^{(\mathrm{ni}+j)\left(2^{r+u-1}\right)}{\mathrm{\&alpha;}}_{i,j}\mathrm{for}0\&le;u\&le;s-1---\left(5\right)$

the situation of r=1.Below for the description to the situation of r=1 wherein and how decode and definite c (m, n, 1, s by syndrome; F (x)) coding whether be the description of PMDS.Parity check matrix H (m, n, r, s that formula (1) is given; F (x)) be written as:

H (m, n, 1, s)=(H ₀(m, n, 1, s), H ₁(m, n, 1, s) ..., H _m-1(m, n, 1, s)), wherein for 0≤j≤m-1

Suppose for integer s _j>=0, if be expert at i at every turn _jin have at most s _jwipe wherein 0≤i for+1 time ₁< i ₂< ... < i _t≤ m-1, c (m, n, 1, s encode; F (x)) be (s ₁+ 1, s ₂+ 1 ..., s _t+ 1)-wipe correction, coding c (m, n, 1, s; F (x)) can correct such wiping.Notice, according to definition 1, and if only if c (m, n, 1, s; F(x)) for the integer s of each selection _j>=1 to such an extent as to be all (s ₁+ 1, s ₂+ 1 ..., s _t+ 1)-entangle when deleting coding c (m, n, 1, s; F (x)) be PMDS.Following lemma has defined when by c (m, n, 1, s; F (x)) be characterized by (s ₁+ 1, s ₂+ 1 ..., s _t+ 1)-entangle and delete.

lemma 1.Consider coding c (m, n, 1, s; F (x)) and make s _j>=1 (1≤j≤t) make for each s _jif, s _jfor odd number, make s ' _j=s _jif, and s _jfor even number, make s ' _j=s _j-1 and therefore, and if only if c (m, n, 1, s '; F (x)) be (s ' ₁+ 1, s ' ₂+ 1 ..., s ' _t+ 1)-entangle delete time, c (m, n, 1, s; F (x)) be (s ₁+ 1, s ₂+ 1 ..., s _t+ 1)-entangle and delete.

lemma 2.Consider coding c (m, n, 1, s; F (x)) and make s _j>=1, each s _j(1≤j≤t) is odd number, and makes therefore, and if only if for any $0\&le;i_2<i_3<\&CenterDot;\&CenterDot;\&CenterDot;<i_t\&le;m-\mathrm{1,0}\&le;l_{j,0}<l_{j,1}<\&CenterDot;\&CenterDot;\&CenterDot;<l_{j,s_j}\&le;n-1(1\&le;j\&le;t),$

C (m, n, 1, s; F (x)) be (s ₁+ 1, s ₂+ 1 ..., s _t+ 1)-entangle and delete.

The combination of lemma 1 and 2 causes following theorem. theorem 1.For s>=1, coding c (m, n, 1, s as given in structure 1; F (x)) be PMDS:(1 when following situation that and if only if) coding c (m, n, 1, s-1; F (x)) be PMDS, and (2) are for making s _jany (s of=s ₁, s ₂..., s _t) and each s _jfor odd number, for any 0≤i ₂< i ₃< ... < i _t≤ m-1 and any $0\&le;l_{j,0}<l_{j,1}<...<l_{j,s_j}\&le;n-1(1\&le;j\&le;t)$ , (6) keep setting up.

theorem 1provide and checked to determine coding c (m, n, 1, s as given in structure 1; F (x)) whether be the condition of PMDS, but any group of PMDS code is not provided himself.Consider with f (x)=1+x+ ... + x ^p-1for the polynomial ring of mould, be prime number and mn < p and make p.Existing irreducible and this ring of f (x) becomes the situation (original function (primitive) in the 2nd, GF (p) equally) in territory.Notice, theorem 1 has the number of times that mostly is mn-1 < p-1=deg (f (x)) most.Therefore,, if f (x) is irreducible, all such polynomial expressions and f (x) are encoded to PMDS for relative prime number and this.This is pointing out as theorem 2 below, and it provides (irreducible polynomial f (the x)=1+x+ of group of PMDS code ... + x ^p-1quantity whether be that infinity is not known).

theorem 2.Consider by structure 1 with f (x)=1+x+ ... + x ^p-1the coding c (m, n, 1, the s that in element fields for mould, provide; F (x)) to make p be prime number and f (x) irreducible (or equally, the original function in the 2nd, GF (p)).C (m, n, 1, s encode; F (x)) be PMDS.

Description so far is disposed the prevailing value of s.Hereinafter, describing may very important special case for application.

the situation of r=1 and s=1: c (m, n, 1,1; F (x))

C (m, n, 1,1; F (x)) be PMDS all the time, because by theorem 1,1+x ^jthe binomial of (1≤j≤n-1) type is relative prime number with f (x).Obviously like this in the time that f (x) is irreducible, and in this case, f (x)=1+x+ ... + x ^p-1be similarly true and make p be that prime number and f (x) are irreducible.This result provides as theorem 3.

theorem 3.Coding c (m, n, 1,1; F (x)) be always PMDS.

the situation of r=1 and s=2: c (m, n, 1,2; F (x))

This situation is important in application, particularly for the array of SSD.Due to c (m, n, 1,1; F (x)) be PMDS, theorem 1 has provided following theorem for the situation of s=2.

theorem 3.For any 1 < i≤m-1 and for any 0≤l _1,0< l _1,1≤ n-1,0≤l _2,0< l _2,1≤ n-1, when following situation that and if only if, coding c (m, n, 1,2; F (x)) be PMDS

$\gcd (1+x^{l_{\mathrm{1,1}}-l_{\mathrm{1,0}}}+x^{\mathrm{in}+l_{\mathrm{2,0}}-l_{\mathrm{1,0}}}(1+x^{l_{\mathrm{2,1}}-l_{\mathrm{2,0}}}),f\left(x\right))=1.---\left(7\right)$

Because this situation is extremely important in application, so here (it is encoded to special case) decoding is at length described a little, other situation is similarly treated.Consider PMDS code c (m, n, 1,2; F (x)), it meets the condition of theorem 4.Without loss of generality in the situation that, suppose to go together mutually i ₀middle existence is wiped for three times, or different rows i ₀and i ₁in have two pairs to wipe, wherein 0≤i ₀< i ₁≤ m-1.Consider wherein to go together mutually i ₀middle appearance is wiped the first situation three times, and the i that is expert at ₀entry j ₀, j ₁and j ₂in, 0≤j ₀< j ₁< j ₂.Initial hypothesis use equation (3) and (5) (equation (4) is only for r > 1), computing syndrome s _mand S _m+1.

Use parity check matrix H (m, n, 1,2) as given in equation (1), solve following linear system:

${\mathrm{\&alpha;}}_{i_0,j_0}\&CirclePlus;{\mathrm{\&alpha;}}_{i_0,j_2}\&CirclePlus;{\mathrm{\&alpha;}}_{i_0,j_2}=S_{i_0}$

${\mathrm{\&alpha;}}^{i_{0}n+j_0}{\mathrm{\&alpha;}}_{i_0,j_0}\&CirclePlus;{\mathrm{\&alpha;}}^{i_{0}n+j_1}{\mathrm{\&alpha;}}_{i_0,j_1}\&CirclePlus;{\mathrm{\&alpha;}}^{i_{0}n+j_2}{\mathrm{\&alpha;}}_{i_0,j_2}=S_m$

${\mathrm{\&alpha;}}^{2(i_{0}n+j_0)}{\mathrm{\&alpha;}}_{i_0,j_0}\&CirclePlus;{\mathrm{\&alpha;}}^{2(i_{0}n+j_1)}{\mathrm{\&alpha;}}_{i_0,j_1}\&CirclePlus;{\mathrm{\&alpha;}}^{2(i_{0}n+j_2)}{\mathrm{\&alpha;}}_{i_0,j_2}=S_{m+1}$

Solution for this system is:

${\mathrm{\&alpha;}}_{i_0,j_0}=\frac{\det \left(\begin{array}{ccc}{S}_{i_0}& 1& 1\\ S_m& {\mathrm{\&alpha;}}^{i_{0}n+j_1}& {\mathrm{\&alpha;}}^{i_{0}n+j_2}\\ S_{m+1}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_1)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_2)}\end{array}\right)}{\det \left(\begin{array}{ccc}1& 1& 1\\ {\mathrm{\&alpha;}}^{i_{0}n+j_0}& {\mathrm{\&alpha;}}^{i_{0}n+j_1}& {\mathrm{\&alpha;}}^{i_{0}n+j_2}\\ {\mathrm{\&alpha;}}^{2(i_{0}n+j_0)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_1)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_2)}\end{array}\right)}$

${\mathrm{\&alpha;}}_{i_0,j_1}=\frac{\det \left(\begin{array}{ccc}1& S_{i_0}& 1\\ {\mathrm{\&alpha;}}^{i_{0}n+j_0}& S_m& {\mathrm{\&alpha;}}^{i_{0}n+j_2}\\ {\mathrm{\&alpha;}}^{2(i_{0}n+j_0)}& S_{m+1}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_2)}\end{array}\right)}{\det \left(\begin{array}{ccc}1& 1& 1\\ {\mathrm{\&alpha;}}^{i_{0}n+j_0}& {\mathrm{\&alpha;}}^{i_{0}n+j_1}& {\mathrm{\&alpha;}}^{i_{0}n+j_2}\\ {\mathrm{\&alpha;}}^{2(i_{0}n+j_0)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_1)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_2)}\end{array}\right)}$

${\mathrm{\&alpha;}}_{i_0,j_2}=\frac{\det \left(\begin{array}{ccc}1& 1& S_{i_0}\\ {\mathrm{\&alpha;}}^{i_{0}n+j_0}& {\mathrm{\&alpha;}}^{i_{0}n+j_1}& S_m\\ {\mathrm{\&alpha;}}^{2(i_{0}n+j_0)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_1)}& S_{m+1}\end{array}\right)}{\det \left(\begin{array}{ccc}1& 1& 1\\ {\mathrm{\&alpha;}}^{i_{0}n+j_0}& {\mathrm{\&alpha;}}^{i_{0}n+j_1}& {\mathrm{\&alpha;}}^{i_{0}n+j_2}\\ {\mathrm{\&alpha;}}^{2(i_{0}n+j_0)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_1)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_2)}\end{array}\right)}$

Due to matrix

$\left(\begin{array}{ccc}1& 1& 1\\ {\mathrm{\&alpha;}}^{i_{0}n+j_0}& {\mathrm{\&alpha;}}^{i_{0}n+j_1}& {\mathrm{\&alpha;}}^{i_{0}n+j_2}\\ {\mathrm{\&alpha;}}^{2(i_{0}n+j_0)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_1)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_2)}\end{array}\right)$

It is Vandermonde matrix

$\det \left(\begin{array}{ccc}1& 1& 1\\ {\mathrm{\&alpha;}}^{i_{0}n+j_0}& {\mathrm{\&alpha;}}^{i_{0}n+j_1}& {\mathrm{\&alpha;}}^{i_{0}n+j_2}\\ {\mathrm{\&alpha;}}^{2(i_{0}n+j_0)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_1)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_2)}\end{array}\right)={\mathrm{\&alpha;}}^{4i_{0}n+3j_0+j_1}(1\&CirclePlus;{\mathrm{\&alpha;}}^{j_1-j_0})(1\&CirclePlus;{\mathrm{\&alpha;}}^{j_2-j_0})(1\&CirclePlus;{\mathrm{\&alpha;}}^{j_2-j_1})$

So the polynomial ring taking 1+x+th as mould as

${\mathrm{\&alpha;}}_{i_0,j_2}=\frac{\det \left(\begin{array}{ccc}1& 1& S_{i_0}\\ {\mathrm{\&alpha;}}^{i_{0}n+j_0}& {\mathrm{\&alpha;}}^{i_{0}n+j_1}& S_m\\ {\mathrm{\&alpha;}}^{2(i_{0}n+j_0)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_2)}& S_{m+2}\end{array}\right)}{\det \left(\begin{array}{ccc}1& 1& 1\\ {\mathrm{\&alpha;}}^{i_{0}n+j_0}& {\mathrm{\&alpha;}}^{i_{0}n+j_1}& {\mathrm{\&alpha;}}^{i_{0}n+j_2}\\ {\mathrm{\&alpha;}}^{2(i_{0}n+j_0)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_1)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_2)}\end{array}\right)}.$

Due to matrix

$\left(\begin{array}{ccc}1& 1& 1\\ {\mathrm{\&alpha;}}^{i_{0}n+j_0}& {\mathrm{\&alpha;}}^{i_{0}n+j_1}& {\mathrm{\&alpha;}}^{i_{0}n+j_2}\\ {\mathrm{\&alpha;}}^{2(i_{0}n+j_0)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_1)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_2)}\end{array}\right)$

It is Vandermonde matrix

$\det \left(\begin{array}{ccc}1& 1& 1\\ {\mathrm{\&alpha;}}^{i_{0}n+j_0}& {\mathrm{\&alpha;}}^{i_{0}n+j_1}& {\mathrm{\&alpha;}}^{i_{0}n+j_2}\\ {\mathrm{\&alpha;}}^{2(i_{0}n+j_0)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_1)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_2)}\end{array}\right)={\mathrm{\&alpha;}}^{4i_{0}n+3j_0+j_1}(1\&CirclePlus;{\mathrm{\&alpha;}}^{j_1-j_0})(1\&CirclePlus;{\mathrm{\&alpha;}}^{j_2-j_0})(1\&CirclePlus;{\mathrm{\&alpha;}}^{j_2-j_1})$

As the skilled person will recognize, for example use the U.S. Patent number 5 of Blaum and Roth, 321, method described in 246 " Method and Means for Coding and Rebuilding the Data Contents Of Unavailable DASDs or Rebuilding the Contents of a DASD in Error in the Presence Of a Reduced Number Of Unavailable DASDs in a DASD Array ", element can be with 1+x+...+x ^p-1for mould, in the polynomial ring that p is prime number, reverse.

Coding is the special case of decoding.For example, suppose two overall parity bits to be placed on position (m-1, n-3) and (m-1, the n-2) in array as shown in Figure 3.Using single parity bit to calculate parity bit α _{i, n-1}(0≤i≤m-2) afterwards, uses method described above to calculate parity bit α _{m-1, n-3}, α _{m-1, n-2}and α _{m-1, n-1}.Especially, Vandermonde determinant becomes and (makes i ₀=m-1, j ₀=n-3, j ₁=n-2 and j ₂=n-1) ${\mathrm{\&alpha;}}^{4(m+n)-15}(1\&CirclePlus;\mathrm{\&alpha;})(1\&CirclePlus;{\mathrm{\&alpha;}}^2)(1\&CirclePlus;\mathrm{\&alpha;})={\mathrm{\&alpha;}}^{4(m+n)-15}(1\&CirclePlus;{\mathrm{\&alpha;}}^4).$ Therefore, only need by reverse to encode, and many computings can calculate in advance, this makes coding very effective.

Another kind of situation is row i ₀and i ₁in have two pairs to wipe, 0≤i ₀< i ₁≤ m-1.In this example, suppose that the entry being wiped free of is row i ₀in with (0≤j ₀< j ₁≤ n-1) and row i ₁in with (0≤l ₀< l ₁≤ n-1).Again, use parity check matrix H (m, n, 1,2), solve the linear system of 4 equatioies with 4 unknown numbers.

${\mathrm{\&alpha;}}_{i_0,j_0}\&CirclePlus;{\mathrm{\&alpha;}}_{i_0,j_1}=S_{i_0}$

${\mathrm{\&alpha;}}_{i_1,l_0}\&CirclePlus;{\mathrm{\&alpha;}}_{i_1,l_1}=S_{i_1}$

${\mathrm{\&alpha;}}^{i_{0}n+j_0}{\mathrm{\&alpha;}}_{i_0,j_0}\&CirclePlus;{\mathrm{\&alpha;}}^{i_{0}n+j_1}{\mathrm{\&alpha;}}_{i_0,j_2}\&CirclePlus;{\mathrm{\&alpha;}}^{i_{2}n+l_0}{\mathrm{\&alpha;}}_{i_2,l_0}\&CirclePlus;{\mathrm{\&alpha;}}^{i_{1}n+l_1}{\mathrm{\&alpha;}}_{i_1,l_1}=S_m$

${\mathrm{\&alpha;}}^{2(i_{0}n+j_0)}{\mathrm{\&alpha;}}_{i_0,j_0}\&CirclePlus;{\mathrm{\&alpha;}}^{2(i_{0}n+j_1)}{\mathrm{\&alpha;}}_{i_0,j_1}\&CirclePlus;{\mathrm{\&alpha;}}^{2(i_{1}n+l_0)}{\mathrm{\&alpha;}}_{i_2,l_0}\&CirclePlus;{\mathrm{\&alpha;}}^{2(i_{1}n+l_1)}{\mathrm{\&alpha;}}_{i_1,l_1}=S_{m+1}$

Wherein with provided by (3), and S _mand S _m+1provided by equation (5).In order to solve this linear system, following determinant is reversed

$\det \left(\begin{array}{cccc}1& 1& 0& 0\\ 0& 0& 1& 1\\ {\mathrm{\&alpha;}}^{i_{0}n+j_0}& {\mathrm{\&alpha;}}^{i_{0}n+j_1}& {\mathrm{\&alpha;}}^{i_{1}n+l_0}& {\mathrm{\&alpha;}}^{i_{2}n+l_1}\\ {\mathrm{\&alpha;}}^{2(i_{0}n+j_0)}& {\mathrm{\&alpha;}}^{2(i_{0}n+j_1)}& {\mathrm{\&alpha;}}^{2(i_{1}n+l_0)}& {\mathrm{\&alpha;}}^{2(i_{1}n+l_1)}\end{array}\right).$

Find out by row operation, this determinant equals following determinant and is multiplied by the power of α:

$\det \left(\begin{array}{cccc}1& 1& 0& 0\\ 0& 0& 1& 1\\ 0& 1\&CirclePlus;{\mathrm{\&alpha;}}^{j_1-j_0}& 0& {\mathrm{\&alpha;}}^{(i_1-i_0)n+l_0-j_0}(1\&CirclePlus;{\mathrm{\&alpha;}}^{l_1-l_0})\\ 0& 1\&CirclePlus;{\mathrm{\&alpha;}}^{2(j_1-j_0)}& 0& {\mathrm{\&alpha;}}^{2((i_1-i_0)n+l_0-j_0)}(1\&CirclePlus;{\mathrm{\&alpha;}}^{2(l_1-l_0)})\end{array}\right)=$

$\det \left(\begin{array}{cc}1\&CirclePlus;{\mathrm{\&alpha;}}^{j_1-j_0}& {\mathrm{\&alpha;}}^{(i_2-i_0)n+l_0-j_0}(1\&CirclePlus;{\mathrm{\&alpha;}}^{l_1-l_0})\\ 1\&CirclePlus;{\mathrm{\&alpha;}}^{2(j_1-j_0)}& {\mathrm{\&alpha;}}^{2((i_1-i_0)n+l_0-j_0)}(1\&CirclePlus;{\mathrm{\&alpha;}}^{2(l_1-l_0)})\end{array}\right)$

Notice, this determinant is corresponding to 2 × 2 Vandermonde matrix, and it equals be multiplied by as previously described, this last expression formula is with f (x)=1+x+ ... + x ^p-1for the ring of mould, in the situation that p is prime number, be easy to reverse.But, right reverse and unlike the reversion binomial going out as shown above neat like that.Due to and 1+x+ ... + x ^p-1due to theorem 4 but relatively prime number, thus use Euclid algorithm to for the f (x) of mould reverses.

This has taken some computing times, but this is not the operation often occurring.In the time there is this situation, degenerating generally can appear due to bust in performance.

Below to some concrete PMDS coding c (m, n, 1,2; F (x)) analysis.Consider first finite field gf (2 ^b).Following table 1 comprises numerical value b, irreducible function f (x) (representing with octal notation), exponent e (f (x)) and coding c (m, n, 1,2; F (x)) be numerical value m and the n of PMDS according to theorem 4.This list be not intended to be all wherein this be encoded to PMDS numerical value exhaustive likely.

Table 1

Next, consider polynomial module f (x)=1+x+ ... + x ^p-1ring, p is prime number and mn < e (f (x))=p.Theorem 2 has solved the wherein irreducible situation of f (x), thereby in this case, supposes that f (x) is irreducible, and this ring is not territory.Consider that for BR code this ring is because wiping of large characters effectively corrected in its permission and uses look-up table unlike in the situation of Galois field.Will for different numerical value m and n, mn < p checks all possible cases of theorem 4.

This result is listed in following table 2, it has provided f between 17 and 257 (x) for its reducible prime number (therefore, 2 in be not the prime number in GF (p)) together with some numerical value of m and n, and indicate whether this coding is the statement of PMDS.For most of these prime numbers, these codings are all PMDS.Only accident is 31,73 and 89.89 situation is interesting especially, and due to for m=8 and n=11 and for m=n=9, this coding is not PMDS.But for m=11 and n=8, this coding is PMDS, it has illustrated and has not only depended on selected polynomial f (x) as the coding of PMDS but also depend on m and n.

Table 2

The situation of r=1 and s=3: c (m, n, 1,3; F (x))

Have two kinds of modes obtain as counting sum s=3, one be 3 self, another kind is 1+1+1.Therefore,, based on theorem 1, theorem 5 is:

theorem 5.C (m, n, 1,3 if encoded when following situation that and if only if; F (x)) be PMDS, c (m, n, 1,2; F (x)) be PMDS, and for 1≤l ₁< l ₂< l ₃≤ n-1,

$\gcd (1+x^{l_1}+x^{l_2}+x^{l_3},f\left(x\right))=1---\left(8\right)$

And for any 1≤i ₂< i ₃≤ m-1,0≤l _1,0< l _1,1≤ n-1,0≤l _2,0< l _2,1≤ n-1 and 0≤l _3,0< l _3,1≤ n-1,

$\gcd (1+x^{l_{\mathrm{1,1}}-l_{\mathrm{1,0}}}+x^{i_{2}n+l_{\mathrm{2,0}}-l_{\mathrm{1,0}}}(1+x^{l_{\mathrm{2,1}}-l_{\mathrm{2,0}}})+x^{i_{3}n+l_{\mathrm{3,0}}-l_{\mathrm{1,0}}}(1+x^{l_{\mathrm{3,1}}-l_{\mathrm{3,0}}}),f\left(x\right))=1---\left(9\right)$

So, in order to check coding c (m, n, 1,3; F (x)) whether be PMDS, first check c (m, n, 1,2; F (x)) whether be PMDS, be similar to above table 1 and 2 listed situations.Whether the equation (8) and (9) that check subsequently to check theorem 5 meet.

For example, the coding in table 1 is c (m, n, 1,2; F (x)) PMDS code, but the equation (9) in theorem 5 has restricted and most of entries and does not correspond to c (m, n, 1,3 very much; F (x)) PMDS code.But, in table 2, as c (m, n, 1,2; F (x)) some codings of PMDS code are also c (m, n, 1,3; F (x)) PMDS code.These results are shown in following table 3, and it shows prime number 17,43,89,127,151,241 and 257 result, but also show 89 result of (m, n)=(11,8) wherein, although they are c (m, n, 1,2; F (x)) PMDS code, but this coding is not c (m, n, 1,3; F (x)).PMDS code.Table 3 shows and makes 2 to be not the numerical value of the p of the prime number in GF (p), and some coding c (m, n, 1,3; F (x)), mn < p.

Table 3

the situation of r=1 and s=4: c(m, n, Isosorbide-5-Nitrae; F (x))

Analysis before being similar to, the institute that s=4 is written as odd number likely and.There are three kinds of modes to do like this: 4=1+3,4=3+1 and 4=1+1+1+1.Therefore,, based on theorem 1, theorem 6 is:

Theorem 6.When following situation that and if only if, coding c (m, n, Isosorbide-5-Nitrae that structure 1 is given; F (x)) be PMDS, coding c (m, n, 1,3; F (x)) be PMDS, and for any 1≤i≤m-1,0≤l _1,0< l _1,1≤ n-1 and 0≤l _2,0< l _2,1< l _2,2< l _2,3≤ n-1,

$\gcd (1+x^{l_{\mathrm{1,1}}-l_{\mathrm{1,0}}}+x^{\mathrm{in}+l_{\mathrm{2,0}}-l_{\mathrm{1,0}}}(1+x^{l_{\mathrm{2,1}}-l_{\mathrm{2,0}}}+x^{l_{\mathrm{2,2}}-l_{\mathrm{2,0}}}+x^{l_{\mathrm{2,3}}-l_{\mathrm{2,0}}}),f\left(x\right))=1,---\left(10\right)$

For any 1≤i≤m-1,0≤l _1,0< l _1,1< l _1,2< l _1,3≤ n-1 and 0≤l _2,0< l _2,1≤ n-1,

$\gcd (1+x^{l_{\mathrm{1,1}}-i_{\mathrm{1,0}}}+x^{l_{\mathrm{1,2}}-l_{\mathrm{1,0}}}+x^{l_{\mathrm{1,3}}-l_{\mathrm{1,0}}}+x^{\mathrm{in}+l_{\mathrm{2,0}}-l_{\mathrm{1,0}}}(1+x^{l_{\mathrm{2,1}}-l_{\mathrm{2,0}}}),f\left(x\right))=1,---\left(11\right)$

And for any 1≤i ₂< i ₃< i ₄≤ m-1,0≤l _1,0< l _1,1≤ n-1,0≤l _2,0< l _2,1≤ n-1,0≤l _3,0< l _3,1≤ n-1 and 0≤l _4,0< l _4,1≤ n-1,

$\begin{array}{c}\gcd (1+x^{l_{\mathrm{1,1}}-l_{1,0}}+x^{i_{2}n+l_{\mathrm{2,0}}-l_{\mathrm{1,0}}}(1+x^{l_{\mathrm{2,1}}-l_{\mathrm{2,0}}})+\\ x^{i_{3}n+l_{\mathrm{3,0}}-l_{\mathrm{1,0}}}(1+x^{l_{\mathrm{3,1}}-l_{\mathrm{3,0}}})+x^{i_{4}n+l_{\mathrm{4,0}}-l_{\mathrm{1,0}}}(1+x^{l_{\mathrm{4,1}}-l_{\mathrm{4,0}}}),f\left(x\right))=1.\end{array}---\left(12\right)$

Consider coding c (m, n, Isosorbide-5-Nitrae; F (x)) the limited situation of lower one.The coding in the present age has been can and have nearly two wrong a line or all have nearly two wrong different rows from the row wiped to recover together by structure.From the viewpoint of coding, simultaneously for 5-entangle delete with (3,3)-entangle c (m, n, the Isosorbide-5-Nitrae deleted; F (x)) coding will complete this task (these conditions are in fact stronger than the coding in same generation because they do not need the row of wiping because wipe can be expert in Anywhere).

Notice, according to lemma 2, and if only if equation (8) is for any 1≤l ₁< l ₂< l ₃≤ n-1 is held in encode c (m, n, Isosorbide-5-Nitrae immediately; F (x)) be that 5-entangles and deletes.And by lemma 2, and if only if equation (7) is for any 1≤i≤m-1 and 0≤l _1,0< l _1,1≤ n-1,0≤l _2,0< l _2,1≤ n-1 is held in immediately, coding c (m, n, Isosorbide-5-Nitrae; F (x)) be (3,3)-entangle and delete.Equation (7) is the condition that coding c (m, n, 1,2) will be served as PMDS completely due to theorem 4.This has caused following lemma.

lemma 3.And if only if coding c (m, n, 1,2; F (x)) be that PMDS and equation (8) are for any 1≤l ₁< l ₂< l ₃≤ n-1 is held in immediately, coding c (m, n, Isosorbide-5-Nitrae; F (x)) be 5-entangle delete and (3,3)-entangle and delete.

As shown in table 2, for c (m, n, 1,2; F (x)) be the m of PMDS, the numerical value of n and p, equation (8) keeps setting up.Therefore, by lemma 3, for such prime number p, coding c (m, n, Isosorbide-5-Nitrae; F (x)) for 5-entangle delete and (3,3)-entangle delete.

the situation of s=1: c (m, n, r, 1; F (x))

So far, the situation of r=1 is described.If r=s=1, as previously described, this is encoded to PMDS.Be the inspection for the situation of r > 1 subsequently.Therefore, suppose row i, 0≤i≤m-1 is in place set to 0≤j ₀< j ₁< ... < j _r≤ n-1 has r+1 time and wipes.Theorem 7 has subsequently provided the condition that this coding will be served as PMDS.

theorem 7.Consider coding c (m, n, r, 1; F (x)).If r is even number, and if only if c (m, n, r-1,1; F (x)) c (m, n, r, 1 while being PMDS; F (x)) be PMDS, and in the time that r is odd number, c when following situation that and if only if (m, n, r, 1; F (x)) be PMDS, c (m, n, r-1,1; F (x)) be PMDS and for any 1≤l ₁< l ₂< ... < l _r≤ n-1,

$\gcd (1+\underset{u=1}{\overset{r}{\mathrm{\&Sigma;}}}{x}^{l_u},f\left(x\right))=1---\left(13\right)$

As previously described, c (m, n, 1,1; F (x)) be PMDS.Therefore, by theorem 7, c (m, n, 2,1; F (x)) be also PMDS.According to equation (13), and if only if (8) for any 1≤l ₁< l ₂< l ₃≤ n-1 and r=3 are held in immediately, c (m, n, 3,1; F (x)) and c (m, n, 4,1; F (x)) be PMDS.

the situation of r=2 and s=1: c (m, n, 2,2; F (x))

For c (m, n, 2,2 that will serve as PMDS; F (x)), its must for 4-entangle delete and (3,3)-entangle delete.As previously described, and if only if equation (8) is for any 1≤l ₁< l ₂< l ₃≤ n-1 is held in immediately, c (m, n, 2,2; F (x)) be that 4-entangles and deletes.And as previously described, this says coding c (m, n, 3,1 in fact; F (x)) be PMDS.By inspection encode c (m, n, 2,2; F (x)) be (3,3)-the entangle condition of deleting, consequently theorem 8.

theorem 8.When following situation that and if only if, coding c (m, n, 2,2; F (x)) be PMDS: if c (m, n, 3,1; F (x)) be PMDS, and for any 1≤i≤m-1,0≤l _1,0< l _1,1< l _1,2≤ n-1 and 0≤l _2,0< l _2,1< l _2,2≤ n-1, if

$\begin{array}{c}g\left(x\right)=1+x^{l_{\mathrm{1,1}}-l_{\mathrm{1,0}}}+x^{l_{1,2}-l_{\mathrm{1,0}}}+x^{2(l_{2,1}-l_{\mathrm{1,0}})}+x^{2(l_{\mathrm{1,2}}-l_{\mathrm{1,0}})}+x^{(l_{\mathrm{1,1}}-l_{\mathrm{1,0}})(l_{\mathrm{1,2}}-l_{\mathrm{1,0}})}+\\ x^{2(\mathrm{in}+l_{\mathrm{2,0}}-l_{\mathrm{1,0}})}(1+x^{l_{\mathrm{2,1}}-l_{\mathrm{2,0}}}+x^{l_{\mathrm{2,2}}-l_{\mathrm{2,0}}}+x^{2(l_{\mathrm{2,1}}-l_{\mathrm{2,0}})}+x^{2(l_{\mathrm{2,2}}-l_{\mathrm{2,0}})}+x^{(l_{\mathrm{2,1}}-l_{\mathrm{2,0}})(l_{\mathrm{2,2}}-l_{\mathrm{2,0}})})\end{array},,$

Gcd (g (x), f (x))=1.

replaceable structure

Below to as the description of the embodiment of the PMDS coding structure of the replacement form of described structure 1 before.

structure 2.Consider the scale-of-two polynomial expression taking f (x) as mould, wherein f (x) is irreducible or f (x)=1+x+ ... + x ^p-1, p is prime number, and makes mn≤e (f (x)).Make c ⁽¹⁾(m, n, r, s; F (x)) be the coding with following (mr+s) × mn parity matrix:

Wherein H (n, r, i, j) is r × n matrix

And 0(n, r) is r × n null matrix.

Next, utilize some examples to describe structure 2.In the first example, m=3 and n=5..:

$H^{\left(1\right)}\left(\mathrm{3,5,1,3}\right)=\left(\begin{array}{ccccccccccccccc}1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1\\ 1& \mathrm{\&alpha;}& {\mathrm{\&alpha;}}^2& {\mathrm{\&alpha;}}^3& {\mathrm{\&alpha;}}^4& {\mathrm{\&alpha;}}^5& {\mathrm{\&alpha;}}^6& {\mathrm{\&alpha;}}^7& {\mathrm{\&alpha;}}^8& {\mathrm{\&alpha;}}^9& {\mathrm{\&alpha;}}^{10}& {\mathrm{\&alpha;}}^{11}& {\mathrm{\&alpha;}}^{12}& {\mathrm{\&alpha;}}^{13}& {\mathrm{\&alpha;}}^{14}\\ 1& {\mathrm{\&alpha;}}^2& {\mathrm{\&alpha;}}^4& {\mathrm{\&alpha;}}^6& {\mathrm{\&alpha;}}^8& {\mathrm{\&alpha;}}^{10}& {\mathrm{\&alpha;}}^{12}& {\mathrm{\&alpha;}}^{14}& {\mathrm{\&alpha;}}^{16}& {\mathrm{\&alpha;}}^{18}& {\mathrm{\&alpha;}}^{20}& {\mathrm{\&alpha;}}^{22}& {\mathrm{\&alpha;}}^{24}& {\mathrm{\&alpha;}}^{26}& {\mathrm{\&alpha;}}^{28}\\ 1& {\mathrm{\&alpha;}}^3& {\mathrm{\&alpha;}}^6& {\mathrm{\&alpha;}}^9& {\mathrm{\&alpha;}}^{12}& {\mathrm{\&alpha;}}^{15}& {\mathrm{\&alpha;}}^{18}& {\mathrm{\&alpha;}}^{21}& {\mathrm{\&alpha;}}^{24}& {\mathrm{\&alpha;}}^{27}& {\mathrm{\&alpha;}}^{30}& {\mathrm{\&alpha;}}^{33}& {\mathrm{\&alpha;}}^{36}& {\mathrm{\&alpha;}}^{39}& {\mathrm{\&alpha;}}^{42}\end{array}\right)$

$H^{\left(1\right)}\left(\mathrm{3,5,3,1}\right)=\left(\begin{array}{ccccccccccccccc}1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& \mathrm{\&alpha;}& {\mathrm{\&alpha;}}^2& {\mathrm{\&alpha;}}^3& {\mathrm{\&alpha;}}^4& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& {\mathrm{\&alpha;}}^2& {\mathrm{\&alpha;}}^4& {\mathrm{\&alpha;}}^6& {\mathrm{\&alpha;}}^8& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& {\mathrm{\&alpha;}}^5& {\mathrm{\&alpha;}}^6& {\mathrm{\&alpha;}}^7& {\mathrm{\&alpha;}}^8& {\mathrm{\&alpha;}}^9& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& {\mathrm{\&alpha;}}^{10}& {\mathrm{\&alpha;}}^{12}& {\mathrm{\&alpha;}}^{14}& {\mathrm{\&alpha;}}^{16}& {\mathrm{\&alpha;}}^{18}& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& {\mathrm{\&alpha;}}^{10}& {\mathrm{\&alpha;}}^{11}& {\mathrm{\&alpha;}}^{12}& {\mathrm{\&alpha;}}^{13}& {\mathrm{\&alpha;}}^{14}\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& {\mathrm{\&alpha;}}^{20}& {\mathrm{\&alpha;}}^{22}& {\mathrm{\&alpha;}}^{24}& {\mathrm{\&alpha;}}^{26}& {\mathrm{\&alpha;}}^{28}\\ 1& {\mathrm{\&alpha;}}^3& {\mathrm{\&alpha;}}^6& {\mathrm{\&alpha;}}^9& {\mathrm{\&alpha;}}^{12}& {\mathrm{\&alpha;}}^{15}& {\mathrm{\&alpha;}}^{18}& {\mathrm{\&alpha;}}^{21}& {\mathrm{\&alpha;}}^{24}& {\mathrm{\&alpha;}}^{27}& {\mathrm{\&alpha;}}^{30}& {\mathrm{\&alpha;}}^{33}& {\mathrm{\&alpha;}}^{36}& {\mathrm{\&alpha;}}^{39}& {\mathrm{\&alpha;}}^{42}\end{array}\right)$

$H^{\left(1\right)}\left(\mathrm{3,5,2,2}\right)=\left(\begin{array}{ccccccccccccccc}1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& \mathrm{\&alpha;}& {\mathrm{\&alpha;}}^2& {\mathrm{\&alpha;}}^3& {\mathrm{\&alpha;}}^4& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& {\mathrm{\&alpha;}}^5& {\mathrm{\&alpha;}}^6& {\mathrm{\&alpha;}}^7& {\mathrm{\&alpha;}}^8& {\mathrm{\&alpha;}}^9& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& {\mathrm{\&alpha;}}^{10}& {\mathrm{\&alpha;}}^{11}& {\mathrm{\&alpha;}}^{12}& {\mathrm{\&alpha;}}^{13}& {\mathrm{\&alpha;}}^{14}\\ 1& {\mathrm{\&alpha;}}^2& {\mathrm{\&alpha;}}^4& {\mathrm{\&alpha;}}^6& {\mathrm{\&alpha;}}^8& {\mathrm{\&alpha;}}^{10}& {\mathrm{\&alpha;}}^{12}& {\mathrm{\&alpha;}}^{14}& {\mathrm{\&alpha;}}^{16}& {\mathrm{\&alpha;}}^{18}& {\mathrm{\&alpha;}}^{20}& {\mathrm{\&alpha;}}^{22}& {\mathrm{\&alpha;}}^{24}& {\mathrm{\&alpha;}}^{26}& {\mathrm{\&alpha;}}^{28}\\ 1& {\mathrm{\&alpha;}}^3& {\mathrm{\&alpha;}}^6& {\mathrm{\&alpha;}}^9& {\mathrm{\&alpha;}}^{12}& {\mathrm{\&alpha;}}^{15}& {\mathrm{\&alpha;}}^{18}& {\mathrm{\&alpha;}}^{21}& {\mathrm{\&alpha;}}^{24}& {\mathrm{\&alpha;}}^{27}& {\mathrm{\&alpha;}}^{30}& {\mathrm{\&alpha;}}^{33}& {\mathrm{\&alpha;}}^{36}& {\mathrm{\&alpha;}}^{39}& {\mathrm{\&alpha;}}^{42}\end{array}\right)$

Note c (m, n, 1,2; ) and c f(x) ⁽¹⁾(m, n, 1,2; F (x)) conflict.It is below the analysis to some special circumstances.

the situation of s=1: c ⁽¹⁾ (m, n, r, 1; F (x))

Now to c ⁽¹⁾(m, n, r, 1; F (x)) be (r+1)-entangle the condition of deleting to test.Use as the defined parity check matrix H of equation (14) ⁽¹⁾(m, n, r, 1), when following situation that and if only if, c ⁽¹⁾(m, n, r, 1; F(x)) (r+1)-and entangle and delete: for any 0≤i≤m-1 and for any 1≤j ₀< j ₁< ... < j _r, Vandermonde determinant

Irreversible.Due to (0≤t < l≤r), in the time that f (x) is irreducible, irreversible.As f (x)=1+x+ ... + x ^p-1, p is prime number and f (x) when reducible, also be irreversible.This has caused theorem 9.

theorem 9.Coding c ⁽¹⁾(m, n, r, 1; F (x)) be PMDS.

Theorem 7 and 9 is compared and reach a conclusion, for r>=2, coding c ⁽¹⁾(m, n, r, 1; F (x)) be better than c (m, n, r, 1; F (x)) because the former is PMDS and not constraint.

the situation of r=1 and s=3: c ⁽¹⁾ (m, n, 1,3; F (x))

Following theorem keeps setting up.

theorem 10.Coding as given in structure 2 c ⁽¹⁾ (m, n, 1,3; F (x))in following situation that and if only if, be PMDS: for any 0≤i ₁≠ i ₂≤ m-1,0≤l _1,0< l _1,1< l _1,2≤ n-1 and 0≤l _2,0< l _2,1≤ n-1, f (α)=0, below matrix be irreversible

$\left(\begin{array}{ccc}1\&CirclePlus;{\mathrm{\&alpha;}}^{l_{\mathrm{1,1}}-l_{\mathrm{1,0}}}& 1\&CirclePlus;{\mathrm{\&alpha;}}^{l_{\mathrm{1,2}}-l_{\mathrm{1,0}}}& {\mathrm{\&alpha;}}^{(i_2-i_1)n+l_{\mathrm{2,0}}-l_{1,0}}(1\&CirclePlus;{\mathrm{\&alpha;}}^{l_{\mathrm{2,2}}-l_{\mathrm{2,0}}})\\ 1\&CirclePlus;{\mathrm{\&alpha;}}^{2(l_{\mathrm{1,1}}-l_{\mathrm{1,0}})}& 1\&CirclePlus;{\mathrm{\&alpha;}}^{2(l_{\mathrm{1,2}}-l_{\mathrm{1,0}})}& {\mathrm{\&alpha;}}^{2((i_2-i_1)n+l_{\mathrm{2,0}}-l_{\mathrm{1,0}})}(1\&CirclePlus;{\mathrm{\&alpha;}}^{2(l_{\mathrm{2,1}}-l_{\mathrm{2,0}})})\\ 1\&CirclePlus;{\mathrm{\&alpha;}}^{3(l_{\mathrm{1,1}}-l_{\mathrm{1,0}})}& 1\&CirclePlus;{\mathrm{\&alpha;}}^{3(l_{\mathrm{1,2}}-l_{\mathrm{1,0}})}& {\mathrm{\&alpha;}}^{3((i_2-i_1)n+l_{\mathrm{2,0}}-l_{1,0})}(1\&CirclePlus;{\mathrm{\&alpha;}}^{3(l_{\mathrm{2,1}}-l_{\mathrm{2,0}})})\end{array}\right)---\left(16\right)$

And for any 1≤i ₂< i ₃≤ m-1,0≤l _1,0< l _1,1≤ n-1,0≤l _2,0< l _2,1≤ n-1 and 0≤l _3,0< l _3,1≤ n-1, below matrix be irreversible

$\left(\begin{array}{ccc}1\&CirclePlus;{\mathrm{\&alpha;}}^{l_{\mathrm{1,1}}-l_{\mathrm{1,0}}}& {\mathrm{\&alpha;}}^{i_{2}n+l_{\mathrm{2,0}}-l_{\mathrm{1,0}}}(1+\&CirclePlus;{\mathrm{\&alpha;}}^{l_{\mathrm{2,1}}-l_{\mathrm{2,0}}})& {\mathrm{\&alpha;}}^{i_{3}n+l_{\mathrm{3,0}}-l_{\mathrm{1,0}}}(1\&CirclePlus;{\mathrm{\&alpha;}}^{l_{\mathrm{3,1}}-l_{\mathrm{3,0}}})\\ 1\&CirclePlus;{\mathrm{\&alpha;}}^{2(l_{\mathrm{1,1}}-l_{\mathrm{1,0}})}& {\mathrm{\&alpha;}}^{2(i_{2}n+l_{\mathrm{2,0}}-l_{\mathrm{1,0}})}(1\&CirclePlus;{\mathrm{\&alpha;}}^{2(l_{\mathrm{2,1}}-l_{\mathrm{2,0}})})& {\mathrm{\&alpha;}}^{2(i_{3}n+l_{\mathrm{3,0}}-l_{\mathrm{1,0}})}(1\&CirclePlus;{\mathrm{\&alpha;}}^{2(l_{\mathrm{3,1}}-l_{\mathrm{3,0}})})\\ 1\&CirclePlus;{\mathrm{\&alpha;}}^{3(l_{\mathrm{1,1}}-l_{\mathrm{1,0}})}& {\mathrm{\&alpha;}}^{2(i_{2}n+l_{\mathrm{2,0}}-l_{\mathrm{1,0}})}(1\&CirclePlus;{\mathrm{\&alpha;}}^{3(l_{\mathrm{2,1}}-l_{\mathrm{2,0}})})& {\mathrm{\&alpha;}}^{3(i_{3}n+l_{\mathrm{3,0}}-l_{\mathrm{1,0}})}(1\&CirclePlus;{\mathrm{\&alpha;}}^{3(l_{\mathrm{3,1}}-l_{\mathrm{3,0}})})\end{array}\right)---\left(17\right)$

Consider f (x)=1+x+ ... + x ^p-1, p is prime number.All make 2 in GF (p) for the prime number p of prime number until p=227 all tested (, f (x) is irreducible), and equation (16) and (17) given matrix are all irreversible in all cases.This has caused lemma 4.

lemma 4.Consider that structure 2 is with f (x)=1+x+ ... + x ^p-1be given coding c on the territory of prime number and f (x) irreducible (or equally, 2 is original function in GF (p)) for mould makes p ⁽¹⁾(m, n, 1,3; F (x)).Therefore, for 19≤p≤227, c ⁽¹⁾(m, n, 1,3; F (x)) be PMDS.

For making 2 to be not the numerical value of antiderivative p in GF (p), in table 4 for the different numerical value of m and n and listed some results.This form and table 3 are closely similar.

Table 4

In fact, table 3 and table 4 are compared, can find out for making c ⁽¹⁾(m, n, 1,3; F (x)) be the p of PMDS, the numerical value of m and n, c (m, n, 1,3; F (x)) be also PMDS.But, for p=23, c (3,7,1,3; F (x)) be PMDS but c ⁽¹⁾(3,7,1,3; F (x)) be not; For p=41, c (5,8,1,3; F (x)) be PMDS but c ⁽¹⁾(5,8,1,3; F (x)) be not; And for p=113, c (3,7,10,11; F (x)), c (3,7,11,10; F (x)) and c (3,7,12,9; F (x)) be PMDS but c ⁽¹⁾(3,7,10,11; F (x)), c ⁽¹⁾(3,7,11,10; F (x)) and c ⁽¹⁾(3,7,12,9; F (x)) be not.

The description that comprises additional code structure and the embodiment to PMDS code is below described.

Technique effect and benefit comprise the PMDS coding of the framework that is applicable to wherein hard error and the simultaneous flash array type of calamitous equipment failure.Here described specific coding useful in application, and PMDS code meets the Necessary and sufficient condition of optimization criteria.The identical protection that can provide with Redundant Array of Independent Disks (RAID) RAID 6 is also provided for technique effect and benefit, but storage efficiency and RAID 5 are close.Therefore, embodiment can be used to make the protection maximization for the band piece fault of given redundancy quantity.

Here the term that used is only for the object that specific embodiment is made an explanation, and is not intended to limit the invention.As used herein, unless context explicitly points out in addition, otherwise term " " (" a ", " an " and " the ") also comprises plural form.Will be to further understand that, in the time using in this instructions, term " comprises " and/or " having comprised " shows to have feature, integer, step, operation, key element and/or the assembly mentioned, exists or increases one or more other feature, integer, step, operation, key element, assembly and/or its groups but do not get rid of.The equivalents of corresponding structure, material, action and all devices or step adds that the functional part in following claim is intended to comprise for carrying out in combination arbitrary structures, material or the action of function with other claimed parts of special requirement protection.Provided for the purpose of illustration and description the description of this invention, but it is not intended to carry out or limits the present invention to disclosed situation exhaustive.Many modifications and variations will be apparent and without departing from the scope and spirit of the present invention for those skilled in the art.Embodiment is selected and describes to principle of the present invention and practical application are made an explanation best, and makes those skilled in the art to understand the present invention for the embodiment with the various amendments that are suitable for desired specific use.

In addition person of ordinary skill in the field knows, various aspects of the present invention can be implemented as system, method or computer program.Therefore, various aspects of the present invention can specific implementation be following form, that is: hardware implementation mode, implement software mode (comprising firmware, resident software, microcode etc.) completely completely, or the embodiment of hardware and software aspect combination, can be referred to as " circuit ", " module " or " system " here.In addition, in certain embodiments, various aspects of the present invention can also be embodied as the form of the computer program in one or more computer-readable mediums, comprise computer-readable program code in this computer-readable medium.

Can adopt the combination in any of one or more computer-readable mediums.Computer-readable medium can be computer-readable signal media or computer-readable recording medium.Computer-readable recording medium for example may be-but not limited to-electricity, magnetic, optical, electrical magnetic, infrared ray or semi-conductive system, device or device, or any above combination.The example more specifically (non exhaustive list) of computer-readable recording medium comprises: have the electrical connection, portable computer diskette, hard disk, random access memory (RAM), ROM (read-only memory) (ROM), erasable type programmable read only memory (EPROM or flash memory), optical fiber, Portable, compact dish ROM (read-only memory) (CD-ROM), light storage device, magnetic memory device of one or more wires or the combination of above-mentioned any appropriate.In presents, computer-readable recording medium can be any comprising or stored program tangible medium, and this program can be used or be combined with it by instruction execution system, device or device.

Computer-readable signal media can be included in the data-signal of propagating in base band or as a carrier wave part, has wherein carried computer-readable program code.The combination of electromagnetic signal that the data-signal of this propagation can adopt various ways, comprises---but being not limited to---, light signal or above-mentioned any appropriate.Computer-readable signal media can also be any computer-readable medium beyond computer-readable recording medium, and this computer-readable medium can send, propagates or transmit the program for being used or be combined with it by instruction execution system, device or device.

The program code comprising on computer-readable medium can be with any suitable medium transmission, comprises that---but being not limited to---is wireless, wired, optical cable, RF etc., or the combination of above-mentioned any appropriate.

Can write the computer program code for carrying out the present invention's operation with the combination in any of one or more programming languages, described programming language comprises object-oriented programming language-such as Java, Smalltalk, C++ etc., also comprises conventional process type programming language-such as " C " language or similar programming language.Program code can fully be carried out, partly on subscriber computer, carries out, carry out or on remote computer or server, carry out completely as an independently software package execution, part part on subscriber computer on remote computer on subscriber computer.In the situation that relates to remote computer, remote computer can be by the network of any kind---comprise LAN (Local Area Network) (LAN) or wide area network (WAN)-be connected to subscriber computer, or, can be connected to outer computer (for example utilizing ISP to pass through Internet connection).

Above with reference to describing the present invention according to process flow diagram and/or the block diagram of the method for the embodiment of the present invention, device (system) and computer program.Should be appreciated that the combination of each square frame in each square frame of process flow diagram and/or block diagram and process flow diagram and/or block diagram, can be realized by computer program instructions.These computer program instructions can offer the processor of multi-purpose computer, special purpose computer or other programmable data treating apparatus, thereby produce a kind of machine, make these computer program instructions in the time that the processor by computing machine or other programmable data treating apparatus is carried out, produced the device of the function/action specifying in the one or more square frames in realization flow figure and/or block diagram.

Also these computer program instructions can be stored in computer-readable medium, these instructions make computing machine, other programmable data treating apparatus or other equipment with ad hoc fashion work, thereby the instruction being stored in computer-readable medium just produces the manufacture (article of manufacture) of the instruction of the function/action specifying in the one or more square frames that comprise in realization flow figure and/or block diagram.

Computer program instructions can also be loaded on computing machine, other programmable data treating apparatus or miscellaneous equipment and make sequence of operations step be able to be carried out on this computing machine, other programmable data treating apparatus or miscellaneous equipment to make to produce the real-time processing of computing machine the instruction carried out on computing machine or other programmable device to be provided for specified function/action in one or more frames of implementing procedure figure and/or block diagram.

Process flow diagram in accompanying drawing and block diagram have shown according to architectural framework in the cards, function and the operation of the system of multiple embodiment of the present invention, method and computer program product.In this, the each square frame in process flow diagram or block diagram can represent a part for module, program segment or a code, and a part for described module, program segment or code comprises one or more for realizing the executable instruction of logic function of regulation.Also it should be noted that what the function marking in square frame also can be marked to be different from accompanying drawing occurs in sequence in some realization as an alternative.For example, in fact two continuous square frames can be carried out substantially concurrently, and they also can be carried out by contrary order sometimes, and this determines according to related function.Also be noted that, the combination of the square frame in each square frame and block diagram and/or process flow diagram in block diagram and/or process flow diagram, can realize by the special hardware based system of the function putting rules into practice or action, or can realize with the combination of specialized hardware and computer instruction.

Claims (25)

1. for store a method for data in the set of n memory device, the method comprises:

Data are write in reception;

This is write to data placement comprising that in the array of the capable and n row entry of m, wherein each entry comprises at least one sector;

Odd even entry is distributed to in mr+s in this array position, and make every a line there is at least r odd even entry, and further make this odd even entry can divide PMDS code corresponding to part ultimate range, this code allow nearly to wipe for r time in the every a line from m is capable and this data array in additionally the wiping and recover for s time of optional position, wherein s is greater than zero integer; And

The odd even entry of this being write to data and be associated is written to the set of this memory device.

2. according to the method for claim 1,

Wherein calculate odd even entry by the linear system that solves mr+s the equation with mr+s unknown number, this linear system is write data and the parity matrix corresponding to PMDS code based on this.

3. according to the process of claim 1 wherein that this writes data and this odd even entry in having the territory or ring of b element, this territory or encircle is generated by the polynomial f (x) of b time, and wherein the product of m and n is less than the index of f (x).

4. according to the method for claim 3, wherein f (x) is polynomial expression M _p(x)=1+x+x ²+ ...+x ^p-1and p is prime number.

5. the method for any one claim before basis, wherein r=1.

6. basis the process of claim 1 wherein that this parity matrix is (m+s) × (mn) matrix, and makes:

J is capable comprises that (j-1) m 0, heel have m 1 and heel to have 0, and wherein j is m to the maximum,

(m+1) row comprises one 1, and heel has α, and heel has α ², etc., until last symbol α of this row ^mn-1, wherein α is the root of f (x), and

(m+i) OK, comprises by exponentiation 2 ^i-1(m+1) row entry, wherein i be 2 and s between number.

7. basis the process of claim 1 wherein that this parity matrix is (m+s) × (mn) matrix, and makes:

J is capable comprises that (j-1) m 0, heel have m 1 and heel to have 0, and wherein j is m to the maximum,

(m+1) row comprises one 1, and heel has α, and heel has α ², etc., until last symbol α of this row ^mn-1, wherein α is the root of f (x), and

(m+i) row comprises by exponentiation i (m+1) row entry, wherein i be 2 and s between number.

8. all just comprise r odd even entry and a line comprises r+s odd even entry according to the process of claim 1 wherein that m-1 is capable.

9. method according to Claim 8, r the odd even entry wherein just comprising in the m-1 of r odd even entry every a line in capable is to use [n, n-r] ultimate range can divide (MDS) code to obtain, and all the other r+s odd even entries are by writing data, the odd even entry that obtained and obtaining corresponding to the system that this parity matrix of PMDS code solves r+s the equation with r+s unknown number before based on this.

10. for store a system for data at storage array, this system comprises:

Comprise the storage array of multiple memory devices; And

Array control unit, it is configured to:

Data are write in reception;

This is write to data placement comprising that in the array of the capable and n row entry of m, wherein each entry comprises at least one sector;

Odd even entry is distributed to in mr+s in this array position, and make every a line there is at least r odd even entry, and further make this odd even entry can divide PMDS code corresponding to part ultimate range, this code allow nearly to wipe for r time in the every a line from m is capable and this data array in additionally the wiping and recover for s time of optional position, wherein s is greater than zero integer; And

The odd even entry of this being write to data and be associated is written to the set of this memory device.

11. according to the system of claim 10, and wherein these data and this odd even entry are in having the territory or ring of b element, and this territory or encircle is generated by the polynomial f (x) of b time, and wherein the product of m and n is less than the index of f (x).

12. according to the system of claim 10, wherein r=1.

13. according to the system of claim 10, and wherein this parity matrix is (m+s) × (mn) matrix, and makes:

J is capable comprises that (j-1) m 0, heel have m 1 and heel to have 0, and wherein j is m to the maximum,

(m+1) row comprises one 1, and heel has α, with there being α ², etc., until last symbol α of this row ^mn-1, wherein α is the root of f (x), and

(m+i) row comprises by exponentiation 2 ^i-1(m+1) row entry, wherein i be 2 and s between number.

14. according to the system of claim 10, and wherein this parity matrix is (m+s) × (mn) matrix, and makes:

J is capable comprises that (j-1) m 0, heel have m 1 and heel to have 0, and wherein j is m to the maximum,

(m+1) row comprises one 1, and heel has α, and heel has α ², etc., until last symbol α of this row ^mn-1, wherein α is the root of f (x),

(m+i) row comprises by exponentiation i (m+1) row entry, wherein i be 2 and s between number.

15. according to the system of claim 10, and wherein m-1 is capable all comprises r odd even entry and a line comprises r+s odd even entry just.

16. according to the system of claim 15, r the odd even entry wherein just comprising in the m-1 of r odd even entry every a line in capable is to use [n, n-r] ultimate range can divide (MDS) code to obtain, and all the other r+s odd even entries are by writing data, the odd even entry that obtained and obtaining corresponding to the system that this parity matrix of PMDS code solves r+s the equation with r+s unknown number before based on this.

17. 1 kinds for storing the computer program of data at storage array, this computer program comprises:

Have the computer-readable recording medium that is recorded in computer readable program code wherein, this computer readable program code comprises:

Computer readable program code, it is configured to:

Data are write in reception;

This is write to data placement comprising that in the array of the capable and n row entry of m, wherein each entry comprises at least one sector;

Odd even entry is distributed to in mr+s in this array position, and make every a line there is at least r odd even entry, and further make this odd even entry can divide PMDS code corresponding to part ultimate range, this code allow nearly to wipe for r time in the every a line from m is capable and this data array in additionally the wiping and recover for s time of optional position, wherein s is greater than zero integer; And

The odd even entry of this being write to data and be associated is written to the set of this memory device.

18. according to the computer program of claim 17, wherein these data and odd even entry are in having the territory or ring of b element, this territory or ring are generated by the polynomial f (x) of b time, and wherein the product of m and n is less than the index of f (x).

19. according to the computer program of claim 17, wherein r=1.

20. according to the computer program of claim 17, and wherein m-1 is capable all comprises r odd even entry and a line comprises r+s odd even entry just.

21. according to the computer program of claim 20, r the odd even entry wherein just comprising in the m-1 of r odd even entry every a line in capable is to use [n, n-r] ultimate range can divide (MDS) code to obtain, and all the other r+s odd even entries are by writing data, the odd even entry that obtained and obtaining corresponding to the system that this parity matrix of PMDS code solves r+s the equation with r+s unknown number before based on this.

22. 1 kinds of methods for wiping of storage array corrected, the method comprises:

Band piece is read in multiple receptions from n memory device, this is read band piece and comprises that capable with m of n is listed as the entry array of arranging, wherein each is listed as corresponding to a memory device, this entry comprises data entry and mr+s odd even entry, and every a line comprises according to part ultimate range can divide PMDS code and at least r odd even entry generating from data entry;

Determine that this reads band piece and comprise that at least one is wiped free of entry, rm+s the entries that are wiped free of at most, and have more than r+s and be wiped free of entry without any row; And

Never be wiped free of entry and be reconstructed being wiped free of entry, this reconstruct produced be resumed read band piece.

23. according to the method for claim 22, and wherein this reconstruct comprises:

Based on not being wiped free of entry and parity matrix computing syndrome in this data array; And

The linear system that solves maximum mr+s the equatioies with maximum mr+s unknown number, this linear system is based on this syndrome and parity matrix.

24. 1 kinds of computer programs for wiping of storage array corrected, this computer program comprises:

Have the computer-readable recording medium that is recorded in computer readable program code wherein, this computer readable program code comprises:

Computer readable program code, it is configured to:

Band piece is read in multiple receptions from n memory device, this is read band piece and comprises that capable with m of n is listed as the entry array of arranging, wherein each is listed as corresponding to a memory device, this entry comprises data entry and mr+s odd even entry, and every a line comprises according to part ultimate range can divide PMDS code and at least r odd even entry generating from data entry;

Determine that this reads band piece and comprise that at least one is wiped free of entry, rm+s the entries that are wiped free of at most, and have more than r+s and be wiped free of entry without any row; And

Never be wiped free of entry and be reconstructed being wiped free of entry, this reconstruct produced be resumed read band piece.

25. according to the computer program of claim 24, and wherein this reconstruct comprises:

Based on not being wiped free of entry and parity matrix computing syndrome in this data array; And

The linear system that solves maximum mr+s the equatioies with maximum mr+s unknown number, this linear system is based on this syndrome and parity matrix.