# US 2017/0288704 A1 · Accelerated erasure coding for storage systems > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2017/0288704 A1 - Document ID: US20170288704A1 - Status: Published application - Kind: A1 - Application number: 15/281,172 - Filed: 2016-09-30 - Published: 2017-10-05 - Earliest claimed: 2016-03-30 - Assignees: EMC IP Holding Company LLC - Applicants: EMC IP Holding Company LLC - Inventors: Maxim Trusov; Mikhail Danilov; Konstantin Buinov; Kirill Zakharov; Andrey Kurilov - Web page: https://patentgrep.com/patent/US20170288704A1 ## CPC - 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} - G06F 11/10: Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's - G06F 11/1012: {using codes or arrangements adapted for a specific type of error (G06F11/1048 takes precedence)} - H03M 13/1515: {Reed-Solomon codes} - 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) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method for generating coded fragments comprises receiving data to be encoded, splitting the data into a plurality of data fragments, identifying a first group of data fragments from among the plurality of data fragments using a coding matrix, summing the data fragments within the first group of data fragments to generate a first group sum, and using the first group sum to calculate at least a portion of two or more coded fragments. ## Claims ### Claim 1 A method comprising: receiving data to be encoded; splitting the data into a plurality of data fragments; identifying a first group of data fragments from among the plurality of data fragments using a coding matrix; summing the data fragments within the first group of data fragments to generate a first group sum; and using the first group sum to calculate at least a portion of two or more coded fragments. ### Claim 2 (depends on 1) The method of claim 1 wherein the coding matrix comprises a binary coding matrix, wherein identifying the first group of data fragments from among the plurality of data fragments comprises counting a number of 1's within rows of the coding matrix. ### Claim 3 (depends on 2) The method of claim 2 wherein summing the data fragments within the first group of data fragments comprising XOR'ing the data fragments within the first group of data fragments. ### Claim 4 (depends on 2) The method of claim 2 further comprising: updating two or more rows of the coding matrix to set 1's to 0's, wherein each of the two or more updated rows of the coding matrix is associated with a corresponding one of the two or more coded fragments. ### Claim 5 (depends on 4) The method of claim 4 further comprising: identifying a second group of data fragments from among the plurality of data fragments using the updated coding matrix; summing the data fragments within the second group of data fragments to generate a second group sum; and using the second group sum to calculate at least a portion of two or more coded fragments. ### Claim 6 (depends on 1) The method of claim 1 wherein identifying the first group of data fragments comprises using a greedy algorithm. ### Claim 7 (depends on 6) The method of claim 6 wherein identifying a group of the data fragments using a greedy algorithm comprises: generating two or more groups of data fragments each having the same number of data fragments; for each of the two or more groups of data fragments, counting a number of coded fragments whose calculations include the sum of the data fragments within the group; and identifying the first group of data fragments as the group of data fragments from among the two or more groups of data fragments having the highest count. ### Claim 8 (depends on 1) The method of claim 1 further comprising: storing the plurality of data fragments and the two or more coded fragments across multiple nodes of a distributed storage system. ### Claim 9 A system comprising: one or more processors; a volatile memory; and a non-volatile memory storing computer program code that when executed on the processor causes execution across the one or more processors of a process operable to perform the operations of: receiving data to be encoded; splitting the data into a plurality of data fragments; identifying a first group of data fragments from among the plurality of data fragments using a coding matrix; summing the data fragments within the first group of data fragments to generate a first group sum; and using the first group sum to calculate at least a portion of two or more coded fragments. ### Claim 10 (depends on 9) The system of claim 9 wherein the coding matrix comprises a binary coding matrix, wherein the computer program code causes execution of a process operable to identify the first group of data fragments from among the plurality of data fragments by counting a number of 1's within rows of the coding matrix. ### Claim 11 (depends on 10) The system of claim 10 wherein the computer program code causes execution of a process operable to sum the data fragments within the first group of data fragments by XOR'ing the data fragments within the first group of data fragments. ### Claim 12 (depends on 10) The system of claim 10 wherein the computer program code causes execution of a process further operable to: update two or more rows of the coding matrix to set 1's to 0's, wherein each of the two or more updated rows of the coding matrix is associated with a corresponding one of the two or more coded fragments. ### Claim 13 (depends on 12) The system of claim 12 wherein the computer program code causes execution of a process further operable to: identify a second group of data fragments from among the plurality of data fragments using the updated coding matrix; sum the data fragments within the second group of data fragments to generate a second group sum; and use the second group sum to calculate at least a portion of two or more coded fragments. ### Claim 14 (depends on 9) The system of claim 9 wherein the computer program code causes execution of a process operable to identify the first group of data fragments using a greedy algorithm. ### Claim 15 (depends on 14) The system of claim 14 wherein the computer program code causes execution of a process operable to identify a group of the data fragments using a greedy algorithm by: generating two or more groups of data fragments each having the same number of data fragments; for each of the two or more groups of data fragments, counting a number of coded fragments whose calculations include the sum of the data fragments within the group; and identifying the first group of data fragments as the group of data fragments from among the two or more groups of data fragments having the highest count. ### Claim 16 (depends on 9) The system of claim 9 wherein the computer program code causes execution of a process further operable to: store the plurality of data fragments and the two or more coded fragments across multiple nodes of a distributed storage system. ### Claim 17 A computer program product tangibly embodied in a non-transitory computer-readable medium, the computer-readable medium storing program instructions that are executable to: receive data to be encoded; split the data into a plurality of data fragments; identify a first group of data fragments from among the plurality of data fragments using a coding matrix; sum the data fragments within the first group of data fragments to generate a first group sum; and use the first group sum to calculate at least a portion of two or more coded fragments.