DNA storage error correction code architecture for optimized decoding

Patent metadata

Field	Value
Publication number	US-12355468-B2
Application number	US-202318528771-A
Country	US
Kind code	B2
Filing date	Dec 4, 2023
Priority date	Dec 4, 2023
Publication date	Jul 8, 2025
Grant date	Jul 8, 2025

Abstract

A DNA-based storage system implements a sub-code architecture for error correction capability (ECC) purposes. The sub-code architecture enables a long DNA strand to be divided into two or more short DNA strands. Each short DNA strand has its own unique parity information. Additionally, each short DNA strand is separately decodable from the other short DNA strands. The parity information associated with a particular short DNA strand is used to correct any errors that occur or are detected during the decoding process. However, if the decoding and error correction processes are not successful using the parity information associated with the particular short DNA strand, global parity information is used to decode the particular short DNA strand and correct the errors. Global parity information includes information from each short DNA strand and the parity information associated with each short DNA strand.

First claim

What is claimed is:

1. A deoxyribonucleic acid (DNA)-based data storage system, comprising:
a control system operable to:
identify a DNA strand for decoding, the DNA strand being associated with global parity information; and

a decoding system operable to:
separate the DNA strand into two or more short DNA strands; and
decode at least one short DNA strand of the two or more short DNA strands using local parity information that is unique to the at least one short DNA strand.

2. The DNA-based data storage system of claim 1 , wherein the decoding system is further operable to:
determine whether the at least one short DNA strand was successfully decoded using the local parity information; and
based, at least in part, on determining that the decoding of the at least one short DNA strand is unsuccessful, decode the at least one short DNA strand using the global parity information.

3. The DNA-based data storage system of claim 1 , wherein the global parity information is generated based, at least in part, on:
the at least one short DNA strand;
the local parity information associated with the at least one short DNA strand;
at least another short DNA strand of the two or more short DNA strands; and
local parity information associated with the at least another short DNA strand.

4. The DNA-based data storage system of claim 3 , wherein the decoding system is further operable to decode the at least one short DNA strand separately from the at least another short DNA strand.

5. The DNA-based data storage system of claim 1 , further comprising an encoding system operable to divide the global parity information between each of the two or more short DNA strands.

6. The DNA-based data storage system of claim 1 , further comprising an encoding system operable to divide system parity information between each of the two or more short DNA strands based, at least in part, on determined performance metrics of the DNA-based data storage system, the system parity information including the global parity information and local parity information associated with each of the two or more short DNA strands.

7. The DNA-based data storage system of claim 1 , wherein the global parity information is configured to correct a first type of error and a second type of error in the at least one short DNA strand.

8. A method of decoding a deoxyribonucleic acid (DNA) strand, comprising:
identifying the DNA strand, the DNA strand being associated with global parity information;
separating the DNA strand into a first short DNA strand and a second short DNA strand;
decoding at least the first short DNA strand with local parity information associated with the first short DNA strand;
determining whether the decoding of the first short DNA strand was successful; and
based, at least in part, on determining that the decoding of first short DNA strand was unsuccessful, decoding the first short DNA strand using the global parity information.

9. The method of claim 8 , wherein the global parity information is generated based, at least in part, on:
the first short DNA strand;
the local parity information associated with the first short DNA strand;
the second short DNA strand; and
local parity information associated with the second short DNA strand.

10. The method of claim 8 , wherein the local parity information associated with the first short DNA strand is unique to the first short DNA strand.

11. The method of claim 8 , further comprising dividing the global parity information between the first short DNA strand and the second short DNA strand.

12. The method of claim 11 , further comprising dividing system parity information between the first short DNA strand and the second short DNA strand based, at least in part, on determined performance metrics of a DNA-based data storage system, the system parity information including the global parity information, the local parity information associated with the first short DNA strand, and local parity information associated with the second short DNA strand.

13. The method of claim 8 , wherein the global parity information corrects insertion/deletion (indel) errors and substitution errors.

14. A deoxyribonucleic acid (DNA)-based data storage system, comprising:
means for decoding a DNA strand using local parity information associated with the DNA strand;
means for determining whether the decoding of the DNA strand was successful; and
means for decoding the DNA strand using global parity information based, at least in part, on a determination that the decoding of the DNA strand using the local parity information was unsuccessful.

15. The DNA-based data storage system of claim 14 , wherein the DNA strand is a first short DNA strand and wherein the DNA-based data storage system further comprises means for separating a long DNA strand into the first short DNA strand and a second short DNA strand.

16. The DNA-based data storage system of claim 15 , wherein the first short DNA strand and the second short DNA strand are each associated with unique parity information.

17. The DNA-based data storage system of claim 15 , wherein the global parity information is based, at least in part, on:
the first short DNA strand;
the local parity information associated with the first short DNA strand;
the second short DNA strand; and
local parity information associated with the second short DNA strand.

18. The DNA-based data storage system of claim 17 , wherein the means for decoding is further operable to decode:
the second short DNA strand; and
the local parity information associated with the second short DNA strand.

19. The DNA-based data storage system of claim 14 , wherein the global parity information is configured to correct one or more of an insertion/deletion (indel) error and a substitution error in the DNA strand.

20. The DNA-based data storage system of claim 14 , further comprising means for encoding the DNA strand, wherein the means for encoding the DNA strand is operable to divide the global parity information between the DNA strand and another DNA strand.

Assignees

• Western Digital Tech Inc

Inventors

• Bazarsky Alexander
• Zamir Ran
• Avraham David

Classifications

• G06N3/123 Primary

  DNA computing · CPC title

• H03M13/611

  Specific encoding aspects, e.g. encoding by means of decoding · CPC title

• H03M13/1102

  Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes · CPC title

• H03M13/1111 Primary

  Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms · CPC title