# US 2010/0169737 A1 · Method and device for multi phase error-correction

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0169737 A1
- Document ID: US20100169737A1
- Status: Published application
- Kind: A1
- Application number: 12/648,313
- Filed: 2009-12-29
- Published: 2010-07-01
- Earliest claimed: 2005-11-15
- Assignees: Ramot at Tel-Aviv University Ltd.
- Inventors: Simon LITSYN; Eran SHARON; Idan ALROD; Menahem LASSER
- Web page: https://patentgrep.com/patent/US20100169737A1

## CPC

- H03M 13/2927: {Decoding strategies}
- G06F 11/1068: {in sector programmable memories, e.g. flash disk (G06F11/1072 takes precedence)}
- H03M 13/1111: {Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms}
- H03M 13/152: {Bose-Chaudhuri-Hocquenghem [BCH] codes}
- H03M 13/1545: {Determination of error locations, e.g. Chien search or other methods or arrangements for the determination of the roots of the error locator polynomial}
- H03M 13/2903: {Methods and arrangements specifically for encoding, e.g. parallel encoding of a plurality of constituent codes}
- H03M 13/2906: {using block codes (H03M13/2957 takes precedence)}
- H03M 13/3715: {Adaptation to the number of estimated errors or to the channel state}
- H03M 13/6362: {by puncturing}
- 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

Data bits to be encoded are split into a plurality of subgroups. Each subgroup is encoded separately to generate a corresponding codeword. Selected subsets are removed from the corresponding codewords, leaving behind shortened codewords, and are many-to-one transformed to condensed bits. The final codeword is a combination of the shortened codewords and the condensed bits. A representation of the final codeword is decoded by being partitioned to a selected subset and a plurality of remaining subsets. Each remaining subset is decoded separately. If one of the decodings fails, the remaining subset whose decoding failed is decoded at least in part according to the selected subset. If the encoding and decoding are systematic then the selected subsets are of parity bits.

## Claims

### Claim 1

A method of providing a scheme for error correction of data bits, the method comprising the steps of
(a) encoding the data bits according to a first encoding scheme to generate a first group of parity bits;
(b) encoding the data bits according to a second encoding scheme to generate a second group of parity bits;
(c) transforming said second group of parity bits into a condensed group of parity bits, wherein said transforming is many-to-one; and
(d) generating a final group of parity bits for the data bits by combining said first group of parity bits with said condensed group of parity bits.

### Claim 2 (depends on 1)

The method of claim 1, wherein said combining of said first group of parity bits with said condensed group of parity bits is effected by steps including assembling at least a portion of said first group of parity bits with said condensed group of parity bits.

### Claim 3 (depends on 1)

The method of claim 1, wherein said transforming step includes XORing a plurality of subgroups of said second group of parity bits.

### Claim 4

A method of providing a scheme for error correction of data bits, the method comprising the steps of
(a) creating a plurality of sub-groups of bits from the data bits, such that each data bit appears at least once in said plurality of sub-groups;
(b) encoding each sub-group of said plurality of sub-groups according to a corresponding first encoding scheme to generate, for each said subgroup, a corresponding at least one first parity bit;
(c) encoding said each sub-group according to a corresponding second encoding scheme to generate, for each said sub-group, a corresponding at least one second parity bit;
(d) transforming all of said at least one second parity bit of all of said plurality of sub-groups into joint condensed parity bits, wherein said transforming is many-to-one; and
(e) generating a final group of parity bits for the data bits by combining all of said at least one first parity bit of all of said plurality of sub-groups with said joint condensed parity bits.

### Claim 5 (depends on 4)

The method of claim 4, wherein said combining of all of said at least one first parity bit of all of said plurality of sub-groups with said joint condensed parity bits is effected by steps including assembling all of said at least one first parity bit of all of said plurality of sub-groups with said joint condensed parity bits.

### Claim 6 (depends on 4)

The method of claim 4, wherein each data bit appears only once in said plurality of subgroups.

### Claim 7 (depends on 4)

The method of claim 4, wherein at least one data bit appears at least twice in said plurality of subgroups.

### Claim 8 (depends on 4)

The method of claim 4, wherein all said sub-groups are of equal size.

### Claim 9 (depends on 4)

The method of claim 4, wherein for at least one sub-group of said plurality of sub-groups said corresponding first encoding scheme and said corresponding second encoding scheme are obtained using a common encoding method, such that said corresponding first encoding scheme encodes bits of said at least one sub-group according to a first order and said corresponding second encoding scheme encodes said bits according to a second order.

### Claim 10 (depends on 4)

The method of claim 4, wherein all said sub-groups are encoded according to a common said first encoding scheme.

### Claim 11 (depends on 4)

The method of claim 4, wherein all said sub-groups are encoded according to a common said second encoding scheme.

### Claim 12 (depends on 4)

The method of claim 4, wherein said transforming step includes XORing said at least one second parity bit corresponding to one of said sub-groups with said at least one second parity bit corresponding to another of said sub-groups.

### Claim 13

A method of providing a scheme for error correction of data bits, the method comprising the steps of
(a) creating a plurality of sub-groups of bits from the data bits, such that each data bit appears at least once in said plurality of sub-groups;
(b) encoding each sub-group of said plurality of sub-groups using a corresponding encoding scheme to generate, for each said sub-group, a corresponding at least one parity bit;
(c) for each said sub-group, selecting a corresponding selected subset from among said bits of said each sub-group and said corresponding at least one parity bit of each said sub-group;
(d) transforming said selected subsets of all of said plurality of sub-groups into joint condensed selected bits, wherein said transforming is many-to-one;
(e) generating a corresponding shortened code word for each said sub-group by combining said bits of each said sub-group with said corresponding at least one parity bit of each said sub-group, and then removing bits of said corresponding selected subset of each said sub-group; and
(f) generating a code word for the data bits by combining said corresponding shortened code word of all of said plurality of sub-groups with said joint condensed selected bits.

### Claim 14 (depends on 13)

The method of claim 13, wherein said combining of said bits of each said sub-group with said corresponding at least one parity bit of each said sub-group is effected by steps including assembling said bits of each said sub-group with said corresponding at least one parity bit of each said sub-group.

### Claim 15 (depends on 13)

The method of claim 13, wherein said combining of said corresponding shortened code word of all of said plurality of sub-groups with said joint condensed selected bits is effected by assembling all of said corresponding shortened code words of said plurality of sub-groups with said joint condensed selected bits.

### Claim 16 (depends on 13)

The method of claim 13, wherein each data bit appears only once in said plurality of subgroups.

### Claim 17 (depends on 13)

The method of claim 13, wherein at least one data bit appears at least twice in said plurality of subgroups.

### Claim 18 (depends on 13)

The method of claim 13, wherein all said sub-groups are of equal size.

### Claim 19 (depends on 13)

The method of claim 13, wherein all said plurality of sub-groups are encoded according to a common said encoding scheme.

### Claim 20 (depends on 13)

The method of claim 13, wherein said transforming step includes XORing the bits of said selected subset corresponding to one of said sub-groups with the bits of said selected subset corresponding to another of said sub-groups.

### Claim 21

A method of providing a scheme for error correction of data bits, said method comprising the steps of:
(a) creating a plurality of sub-groups of bits from the data bits, such that each data bit appears at least once in said sub-groups;
(b) encoding each of said plurality of sub-groups using a corresponding encoding scheme to generate, for each said sub-group, a corresponding code word;
(c) for each said sub-group, selecting a corresponding selected subset from bits of said corresponding code word;
(d) transforming said corresponding selected subsets of all of said corresponding code words into joint condensed selected bits, wherein said transforming is many-to-one;
(e) generating a corresponding shortened code word for each of said corresponding code words by removing bits of said selected subset corresponding to each said corresponding code word; and
(f) generating a code word for the data bits by combining said corresponding shortened code word of all of said plurality of sub-groups with said joint condensed selected bits.

### Claim 22 (depends on 21)

The method of claim 21, wherein said combining of said corresponding shortened code words of all of said plurality of sub-groups with said joint condensed selected bits is effected by assembling all of said corresponding shortened code words of said plurality of sub-groups with said joint condensed selected bits.

### Claim 23 (depends on 21)

The method of claim 21, wherein each data bit appears only once in said plurality of subgroups.

### Claim 24 (depends on 21)

The method of claim 21, wherein at least one data bit appears at least twice in said plurality of subgroups.

### Claim 25 (depends on 21)

The method of claim 21, wherein all said sub-groups are of equal size.

### Claim 26 (depends on 21)

The method of claim 21, wherein all of said plurality of sub-groups are encoded according to a common said encoding scheme.

### Claim 27 (depends on 21)

The method of claim 21, wherein said transforming step includes XORing the bits of said selected subset corresponding to one of said sub-groups with the bits of said selected subset corresponding to another of said sub-groups.

### Claim 28

A method of decoding a representation of a code word, the representation containing M data bits and P parity bits, the method comprising the steps of:
(a) partitioning the P parity bits into a first group of parity bits and a second group of parity bits;
(b) decoding the M data bits using only said first group of parity bits to provide corrected data bits; and
(c) if said decoding using only said first group of parity bits fails, then decoding the M data bits using said first group of parity bits and said second group of parity bits to provide said corrected data bits.

### Claim 29

A method of decoding a representation of a code word containing M data bits and P parity bits, the method comprising the steps of:
(a) partitioning the M data bits into K>1 subsets, wherein each of the M data bits appears at least once in said K subsets;
(b) partitioning the P parity bits into a first group of parity bits and a second group of parity bits;
(c) partitioning said first group of parity bits into K subsets each said subset of said first group of parity bits corresponding to a respective subset of the M data bits;
(d) decoding each said subset of the M data bits according to said corresponding subset of said first group of parity bits to generate decoded data of said each subset of the M data bits;
(e) if said decoding of one of said K subsets of the M data bits fails: decoding said one subset according to, at least in part, said second group of parity bits to generate said decoded data of said one subset; and
(f) combining said decoded data of all of said K subsets of the M data bits to generate total decoded data for the M data bits.

### Claim 30 (depends on 29)

The method of claim 29, wherein said combining of said decoded data of all said K subsets of the M data bits is effected by assembling said decoded data of all said K subsets of the M data bits.

### Claim 31 (depends on 29)

The method of claim 29, wherein said K subsets of the M data bits are disjoint.

### Claim 32 (depends on 29)

The method of claim 29, wherein said K subsets of the M data bits are all of equal size.

### Claim 33 (depends on 29)

The method of claim 29, wherein said decoding of the data bits of said each subset according to said corresponding subset of said first group of parity bits includes using a corresponding first decoding scheme, and wherein said decoding of the data bits of said one subset, whose decoding failed, according to said second group of parity bits includes using a corresponding second decoding scheme.

### Claim 34 (depends on 42)

The method of claim 42, wherein for at least one of said K subsets of the M data bits said corresponding first decoding scheme and said corresponding second decoding scheme apply a common decoding method.

### Claim 35 (depends on 42)

The method of claim 42, wherein all said first decoding schemes are identical.

### Claim 36 (depends on 42)

The method of claim 42, wherein all said second decoding schemes are identical.

### Claim 37

A method of decoding M data bits out of a representation of a code word, that has N>M bits, the method comprising the steps of:
(a) removing a selected subset of at most N-M bits from the N bits, thereby producing a set of remaining bits;
(b) partitioning said remaining bits into K>1 subsets of said remaining bits, wherein each of said remaining bits is a member of at least one of said K subsets;
(c) decoding each of said K subsets according only to bits of said each subset to generate decoded data of said each subset;
(d) if said decoding of one of said K subsets fails: decoding said one subset, at least in part, according to said removed selected subset to generate said decoded data of said one subset; and
(e) combining said decoded data of all of said K subsets to generate total decoded data for the M data bits.

### Claim 38 (depends on 37)

The method of claim 37, wherein said combing of said decoded data of all said K subsets is effected by assembling all of said decoded data of all said K subsets.

### Claim 39 (depends on 37)

The method of claim 37, wherein said K subsets are disjoint.

### Claim 40 (depends on 37)

The method of claim 37, wherein said K subsets are all of equal size.

### Claim 41 (depends on 37)

The method of claim 37, wherein said decoding of the data bits of said each subset according to said bits of said each subset includes using a corresponding first decoding scheme, and wherein said decoding of the data bits of said one subset whose decoding failed according to said removed selected subset includes using a corresponding second decoding scheme.

### Claim 42 (depends on 41)

The method of claim 41, wherein for at least one of said K subsets said corresponding first decoding scheme and said corresponding second decoding scheme apply a common decoding method.

### Claim 43 (depends on 41)

The method of claim 41, wherein all said first decoding schemes are identical.

### Claim 44 (depends on 41)

The method of claim 41, wherein all said second decoding schemes are identical.
