# US 2023/0053467 A1 · Encoding for data recovery in storage systems > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2023/0053467 A1 - Document ID: US20230053467A1 - Status: Published application - Kind: A1 - Application number: 17/790,493 - Filed: 2020-12-14 - Published: 2023-02-23 - Earliest claimed: 2020-01-09 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Technology Licensing, LLC - Inventors: Christos GKANTSIDIS; Antony Ian Taylor ROWSTRON; Andromachi CHATZIELEFTHERIOU; Richard John BLACK; Austin N. DONNELLY; István HALLER - Web page: https://patentgrep.com/patent/US20230053467A1 ## CPC - H03M 13/13: Linear codes - H03M 13/616: {Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations} - G06F 11/1076: {Parity data used in redundant arrays of independent storages, e.g. in RAID systems} - H03M 13/1515: {Reed-Solomon codes} - 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/611: {Specific encoding aspects, e.g. encoding by means of decoding} - 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 of reading from a storage medium to recover a group of information sectors, each comprising a respective information payload. The medium stores redundancy data comprising a plurality of separate redundancy codes for the group, each code being a linear sum of terms, each term in the sum being the information payload from a different respective one of the information sectors in the group weighted by a respective coefficient of a set of coefficients for the redundancy code. The method comprises, after the redundancy data has already been stored on the medium: identifying a set of k′ information sectors to be recovered; selecting k′ of the redundancy codes; determining a square matrix E of the k′ information sectors by the k′ sets of coefficients of the selected codes; determining a matrix D being a matrix inverse of E; and recovering the k′ information payloads from the inverse matrix D. ## Claims ### Claim 1 A computer-implemented method of reading from a storage medium in order to recover a group of information sectors, each information sector comprising a respective information payload; wherein the storage medium stores redundancy data comprising a plurality of separate redundancy codes for said group, each redundancy code being a linear sum of terms, each term in the sum being the information payload from a different respective one of the information sectors in said group weighted by a respective coefficient of a set of coefficients for the redundancy code, wherein said coefficients are selected according to a pseudorandom process; and wherein the method comprises, after the redundancy data has already been stored on the storage medium, performing a decoding process comprising: identifying a set of k′ information sectors from said group from which the respective information payloads are to be recovered based on the redundancy data; selecting k′ of the redundancy codes; determining a square matrix E in which each matrix column comprises the respective coefficients of a different one of the k′ information sectors, and each matrix row comprises the set of coefficients of a different one of the k′ redundancy codes, or vice versa; determining a matrix D being a matrix inverse of E; and recovering the k′ information payloads by computing: νi=Σj(dd,j·rj), where vi is the information payload, i is an index denoting the respective information sector, and j is an index denoting each redundancy code rj, and where di,j are the matrix elements of the D, and Σj is the sum over the k′ redundancy codes, the computation being performed for i of each of the k′ information sectors. ### Claim 2 (depends on 1) The method of claim 1, some or all of the information sectors are also stored on the storage medium. ### Claim 3 (depends on 2) The method of claim 2, wherein said identifying comprises: identifying which of the group of the information sectors are missing or erroneous, not being present on the storage medium or having information payloads νi that contain errors, and identifying which are present and non-erroneous, being found present on the storage medium and having information payloads νi that do not contain errors, wherein the k′ information sectors comprise the missing and/or erroneous information sectors of the group. ### Claim 4 (depends on 3) The method of claim 3, wherein the k′ information sectors are only the missing and/or erroneous sectors of the group. ### Claim 5 (depends on 3) The method of claim 3, comprising: prior to said recovery, updating each of k′ of the redundancy codes by performing rj←rj−(cj,i·vi) over i of all non-erroneous information sectors in the group that are found stored on the storage medium, where cj,i is the coefficient corresponding to the ith information sector and jth redundancy code; wherein the redundancy codes rj used in said recovery are the updated redundancy codes. ### Claim 6 (depends on 1) The method of claim 1, wherein the sets of coefficients are not stored on the storage medium, and instead the method comprises: reading from the storage medium an indication of a predetermined deterministic process for determining the sets of coefficients, and based thereon using said process to determine the sets of coefficients, or receiving the sets of coefficients via a separate medium, or receiving via a separate medium an indication of a predetermined deterministic process for determining the sets of coefficients, and based thereon using said process to determine the sets of coefficients. ### Claim 7 (depends on 1) The method of claim 1, wherein the sets of coefficients for the different redundancy codes are linearly independent with respect to one another. ### Claim 8 (depends on 1) The method of claim 1, comprising an initial stage of storing the redundancy codes on the storage medium prior to said decoding process, wherein the initial storing stage comprises selecting the coefficients according to a process that ensures the sets of coefficients for the different redundancy codes are linearly independent with respect to one another. ### Claim 9 (depends on 1) The method of claim 1, comprising an initial stage of storing the redundancy codes on the storage medium prior to said decoding process, wherein the initial storing stage comprises the selecting of the coefficients pseudorandomly according to said pseudorandom process. ### Claim 10 (depends on 1) The method of claim 1, wherein said group of information sectors is all the information sectors on the storage medium. ### Claim 11 (depends on 1) The method of claim 1, wherein said group of information sectors is one of multiple groups of information sectors on the storage medium, and the method is applied individually to each of said groups. ### Claim 12 (depends on 11) The method of any-preceding claim 11, wherein the information sectors from different ones of the groups are physically interleaved on the storage medium. ### Claim 13 (depends on 1) The method of claim 1, wherein said group of information sectors is one of a first group of information sectors stored on the storage medium and a second group of information sectors stored on the storage medium overlapping with the first, including some but not all of the same information sectors, each of the first and second groups being associated with a respective set of redundancy codes; wherein the method comprises: when the information payloads of all the information sectors in the first group cannot initially be recovered based on the respective set of redundancy codes associated with the first group, recovering the information payloads of the information sectors in the second group based on the respective set of redundancy codes associated with the second group, thus recovering at least one of the payloads of the information sectors overlapping with the first group; and subsequently recovering the first group based on the redundancy sectors associated with the first group and the at least one recovered information sector in the first group. ### Claim 14 (depends on 1) The method of claim 1, wherein the storage medium comprises multiple separate pieces of writeable material, wherein said information sectors and/or redundancy codes span the multiple pieces of writeable material. ### Claim 15 A computer program embodied on computer-readable storage and comprising code configured so as when run on one or more processing units to perform the method of reading from a storage medium in order to recover a group of information sectors, each information sector comprising a respective information payload; wherein the storage medium stores redundancy data comprising a plurality of separate redundancy codes for said group, each redundancy code being a linear sum of terms, each term in the sum being the information payload from a different respective one of the information sectors in said group weighted by a respective coefficient of a set of coefficients for the redundancy code, wherein said coefficients are selected according to a pseudorandom process; and wherein the method comprises, after the redundancy data has already been stored on the storage medium, performing a decoding process comprising: identifying a set of k′ information sectors from said group from which the respective information payloads are to be recovered based on the redundancy data; selecting k′ of the redundancy codes; determining a square matrix E in which each matrix column comprises the respective coefficients of a different one of the k′ information sectors, and each matrix row comprises the set of coefficients of a different one of the k′ redundancy codes, or vice versa; determining a matrix D being a matrix inverse of E; and recovering the k′ information payloads by computing: νi=Σj(di,j·rj), where νi is the information payload, i is an index denoting the respective information sector, and j is an index denoting each redundancy code r1, and where di,j are the matrix elements of the D, and Σj is the sum over the k′ redundancy codes, the computation being performed for i of each of the k′ information sectors.