# US 10,122,381 B2 · Method of constructing flat XOR codes from integer indexed tanner graphs > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,122,381 B2 - Document ID: US10122381B2 - Status: Granted - Kind: B2 - Application number: 15/508,718 - Filed: 2015-09-29 - Published: 2017-09-28 - Granted: 2018-11-06 - Earliest claimed: 2014-10-03 - Assignees: Agency for Science, Technology and Research - Applicants: Agency For Science, Technology And Research - Inventors: Chao Jin; Weiya Xi; Khai Leong Yong; Shibin Chen - Web page: https://patentgrep.com/patent/US10122381B2 ## CPC - H03M 13/1102: {Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes} - H03M 13/036: {Heuristic code construction methods, i.e. code construction or code search based on using trial-and-error} - H03M 13/373: {with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes} - H03M 13/05: using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits {(H03M13/2906 takes precedence)} - H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C) ## Abstract A method for defining an erasure code for system having a predetermined number of data disks is disclosed. The method includes selecting step, constructing step, determining step and repeating step. The selecting step includes selecting a predetermined acceptable number of failures for the system. The constructing step includes constructing a first Tanner graph for two failures acceptable system having predetermined number of data disks. The determining step includes determining erasure code from the first Tanner graph. The repeating step includes repeating the constructing step and the determining step by increasing the acceptable number of failures by one and constructing another Tanner graph in response to the increased acceptable number of failures by increasing number of parity nodes until the predetermined number of failures for the system is reached. ## Claims ### Claim 1 A method comprising: improving data recovery upon a disk failure in a system having a predetermined number of data disks in which constructed erasure codes (INT-codes) are flat XOR erasure code by: selecting a predetermined acceptable number of failures for the system; constructing a first Tanner graph for a two failures acceptable system having the predetermined number of data disks; determining a first erasure code from the first Tanner graph; and repeating the constructing step and the determining step by increasing the predetermined acceptable number of failures by one and (a) constructing another Tanner graph in response to increasing the predetermined acceptable number of failures and an increased number of parity nodes and (b) determining a subsequent erasure code from the another Tanner graph, wherein the constructing another Tanner graph and the determining the subsequent erasure code repeat until an erasure code is determined for the predetermined acceptable number of failures for the system, and wherein the erasure code is flat XOR code in which each strip includes only one element of either data or parity, Tanner graphs constructed from the method include an index for each symbol node that represents either a data symbol or a parity symbol, and encoding and decoding of the erasure code are based on integer indices in the Tanner graphs constructed from the method. ### Claim 2 (depends on 1) The method in accordance with claim 1, wherein the step of constructing a first Tanner graph for a two failures acceptable system comprises: determining a number of data nodes based on the predetermined number of data disks; determining a number of parity nodes required in the system based on the number of data nodes; determining a number of symbol nodes in the first Tanner graph in response to a sum of the number of data nodes and the number of parity nodes; determining a number of check nodes in the first Tanner graph from the number of parity nodes; and constructing the first Tanner graph for the two failures acceptable system by using the number of symbol nodes and the number of check nodes. ### Claim 3 (depends on 2) The method in accordance with claim 2, wherein the step of determining a number of parity nodes required in the system comprises: A) choosing an integer set as node indices; B) determining a number of digits in a node index so that each node in the node index has a unique index; and C) computing the number of parity nodes. ### Claim 4 (depends on 1) The method in accordance with claim 1, wherein the repeating step further comprises adding both the increased number of parity nodes and an increased number of check nodes into the first Tanner graph to construct a system that tolerates more than three node failures. ### Claim 5 (depends on 1) The method in accordance with claim 1, wherein the repeating step further comprises adding both the increased number of parity nodes and an increased number of check nodes into the first Tanner graph to construct a four failures acceptable system. ### Claim 6 (depends on 1) The method in accordance with claim 1, wherein the repeating step further comprises adding both the increased number of parity nodes and an increased number of check nodes into the first Tanner graph to construct a more than four failures acceptable system. ### Claim 7 (depends on 3) The method in accordance with claim 3, wherein the integer set chosen as the node indices in the first Tanner graph are binary integers. ### Claim 8 (depends on 3) The method in accordance with claim 3, wherein the integer set chosen as the node indices in the first Tanner graph are q-ary (base q) integers. ### Claim 9 A non-transient computer readable medium containing program instructions for causing a computer to execute a method comprising: improving data recovery upon a disk failure in a system having a predetermined number of data disks in which constructed erasure codes (INT-codes) are flat XOR erasure code by: selecting a predetermined acceptable number of failures for the system; constructing a first Tanner graph for a two failures acceptable system having the predetermined number of data disks; determining a first erasure code from the first Tanner graph; and repeating the constructing step and the determining step by increasing the predetermined acceptable number of failures by one and (a) constructing another Tanner graph in response to increasing the predetermined acceptable number of failures and an increased number of parity nodes and (b) determining a subsequent erasure code from the another Tanner graph, wherein the constructing another Tanner graph and the determining the subsequent erasure code repeat until an erasure code is determined for the predetermined number of failures for the system, and wherein the erasure code is flat XOR code in which each strip includes only one element of either data or parity, Tanner graphs constructed from the method include an index for each symbol node that represents either a data symbol or a parity symbol, and encoding and decoding of the erasure code are based on integer indices in the Tanner graphs constructed from the method. ### Claim 10 A system comprising: an apparatus having a predetermined number of data disks; and a computer for defining a flat XOR erasure code, having a processor configured to improve data recovery when one of the data disks fails by: select a predetermined acceptable number of failures for the system; construct a first Tanner graph for a two failures acceptable system having the predetermined number of data disks; determine a first erasure code from the first Tanner graph; and repeat the constructing step and the determining step by increasing the predetermined acceptable number of failures by one and (a) constructing another Tanner graph in response to increasing the predetermined acceptable number of failures and an increased number of parity nodes and (b) determining a subsequent erasure code from the another Tanner graph, wherein the constructing another Tanner graph and the determining the subsequent erasure code repeat until an erasure code is determined for the predetermined number of failures for the system, and wherein the erasure code is flat XOR code in which each strip includes only one element of either data or parity, Tanner graphs constructed from the computer include an index for each symbol node that represents either a data symbol or a parity symbol, and encoding and decoding of the erasure code are based on integer indices in the Tanner graphs constructed from the computer.