IPC분류정보
국가/구분 |
United States(US) Patent
등록
|
국제특허분류(IPC7판) |
|
출원번호 |
US-0675981
(2008-12-12)
|
등록번호 |
US-8407553
(2013-03-26)
|
국제출원번호 |
PCT/US2008/086523
(2008-12-12)
|
§371/§102 date |
20100302
(20100302)
|
국제공개번호 |
WO2010/019168
(2010-02-18)
|
발명자
/ 주소 |
|
출원인 / 주소 |
|
대리인 / 주소 |
Mendelsohn, Drucker & Associates, P.C.
|
인용정보 |
피인용 횟수 :
1 인용 특허 :
48 |
초록
▼
Certain embodiments of the present invention are efficient run-time methods for creating and updating a RAM list of dominant trapping-set profiles for use in (LDPC) list decoding. A decoded correct codeword is compared to a near codeword to generate a new trapping-set profile, and the profile writte
Certain embodiments of the present invention are efficient run-time methods for creating and updating a RAM list of dominant trapping-set profiles for use in (LDPC) list decoding. A decoded correct codeword is compared to a near codeword to generate a new trapping-set profile, and the profile written to RAM. Record is kept of how many times RAM has been searched since a profile was last matched. Profiles that have not been matched within a specified number of searches are purge-eligible. Purge-eligible profiles are further ranked on other factors, e.g., number of times a profile has been matched since it was added, number of unsatisfied check nodes, number of erroneous bit nodes. If there is insufficient free space in RAM to store a newly-discovered profile, then purge-eligible profiles are deleted, beginning with the lowest-ranked profiles, until either (i) sufficient free space is created or (ii) there are no more purge-eligible profiles.
대표청구항
▼
1. A method for decoding encoded data encoded with a graph-based code, the method comprising: (a) performing decoding on the encoded data to generate a candidate decoded codeword; and(b) performing, if the candidate decoded codeword is not a decoded correct codeword, a trapping-set RAM list-decoding
1. A method for decoding encoded data encoded with a graph-based code, the method comprising: (a) performing decoding on the encoded data to generate a candidate decoded codeword; and(b) performing, if the candidate decoded codeword is not a decoded correct codeword, a trapping-set RAM list-decoding method to attempt to generate the decoded correct codeword, wherein the trapping-set-RAM list-decoding method accesses one or more trapping-set profiles stored in RAM memory, each trapping-set profile corresponding to a different trapping set. 2. The invention method of claim 1, further comprising: (c) updating the RAM memory to store a new trapping-set profile. 3. The method of claim 2, wherein: if the trapping-set-RAM list decoding fails to generate the decoded correct codeword, then step (b) further comprises performing an other decoding method to attempt to generate the decoded correct codeword; andif the other decoding method generates the decoded correct codeword, then step (c) comprises generating the new trapping-set profile based on the candidate decoded codeword and the decoded correct codeword. 4. The method of claim 2, wherein step (c) comprises: (c1) selecting, for purging, one or more trapping-set profiles previously stored in the RAM memory;(c2) purging the selected one or more trapping-set profiles from the RAM memory; and(c3) storing the new trapping-set profile in the RAM memory. 5. The method of claim 4, wherein step (c1) comprises selecting a trapping-set profile for purging based on one or more of: (i) a number of times the RAM memory has been searched during previous performances of the trapping-set-RAM list-decoding method since the selected trapping-set profile has been matched during previous performances of the trapping-set-RAM list-decoding method;(ii) a total number of times that the selected trapping-set profile has been matched during previous performances of the trapping-set-RAM list-decoding method since the selected trapping-set profile was stored in the RAM memory;(iii) a number of unsatisfied check nodes in the selected trapping-set profile; and(iv) a number of erroneous bit nodes in the selected trapping-set profile. 6. The method of claim 5, wherein step (c1) comprises selecting the trapping-set profile for purging based on the number of times the RAM memory has been searched during previous performances of the trapping-set-RAM list-decoding method since the selected trapping-set profile has last been matched during previous performances of the trapping-set-RAM list-decoding method. 7. The method of 4, wherein step (c1) comprises searching the stored trapping-set profiles in a sequence specified by a separate RAM Index Table. 8. The method of claim 1, wherein each trapping-set profile comprises: a number of unsatisfied check nodes in the corresponding trapping set;identification of each unsatisfied check node in the corresponding trapping set; andidentification of at least one erroneous bit node for each unsatisfied check node in the corresponding trapping set. 9. The method of claim 8, wherein each trapping-set profile further comprises: a number of erroneous bit nodes in the corresponding trapping set;a number of times that the trapping-set profile has been matched during previous performances of the trapping-set-RAM list-decoding method since the trapping-set profile was stored in the RAM memory; andthe number of the most recent performance of the trapping-set-RAM list-decoding method that matched this particular profile. 10. The method of claim 1, wherein: if the candidate decoded codeword is not the decoded correct codeword, then the candidate decoded codeword identifies an observed trapping set comprising a set of one or more observed unsatisfied check nodes; andthe trapping-set-RAM list-decoding method comprises: (b1) searching through the RAM memory for a stored trapping-set profile that matches the observed trapping set;(b2) modifying one or more erroneous bit nodes for the low-density parity-check-encoded data, wherein the one or more modified erroneous bit nodes are identified by the matched trapping-set profile; and(b3) performing low-density parity-check decoding on the modified low-density parity-check-encoded data. 11. The method of claim 10, wherein the stored trapping-set profile matches the observed trapping set when the one or more unsatisfied check nodes of the stored trapping-set profile form an isomorphic match with the one or more observed unsatisfied check nodes of the observed trapping set. 12. The method of claim 10, wherein step (b1) comprises searching the stored trapping-set profiles in a sequence specified by a separate RAM Index Table. 13. The method of claim 1, further comprising: (c) sorting the trapping-set profiles stored in the RAM memory based on dominance of the corresponding trapping sets. 14. The method of claim 13, wherein the dominance of a trapping set is based on one or more of: (i) a number of times the RAM memory has been searched during previous performances of the trapping-set-RAM list-decoding method since the corresponding trapping-set profile has been matched during previous performances of the trapping-set-RAM list-decoding method;(ii) a total number of times that the corresponding trapping-set profile has been matched during previous performances of the trapping-set-RAM list-decoding method since the corresponding trapping-set profile was stored in the RAM memory;(iii) a number of unsatisfied check nodes in the trapping set; and(iv) a number of erroneous bit nodes in the trapping set. 15. The method of claim 14, wherein a first trapping set having a first trapping-set profile is more dominant than a second trapping set having a second trapping-set profile if (i) the number of times the RAM memory has been searched during previous performances of the trapping-set-RAM list-decoding method since the first trapping-set profile has been matched during previous performances of the trapping-set-RAM list-decoding method is less than (ii) the number of times the RAM memory has been searched during previous performances of the trapping-set-RAM list-decoding method since the second trapping-set profile has been matched during previous performances of the trapping-set-RAM list-decoding method. 16. The method of claim 13, further comprising: (d) storing the addresses of the sorted trapping-set profiles in a separate RAM Index Table such that the order of the addresses in the separate RAM index table is based on the sorting results of step (c). 17. The method of claim 1, wherein the graph-based code is a Low-Density Parity Check code. 18. An apparatus for decoding encoded data encoded with a graph-based code, the apparatus comprising: a decoder adapted to perform decoding on the encoded data to generate a candidate decoded codeword;RAM memory; anda trapping-set RAM list decoder adapted to perform, if the candidate decoded codeword is not a decoded correct codeword, a trapping-set-RAM list-decoding method to attempt to generate the decoded correct codeword, wherein the trapping-set-RAM list decoder accesses one or more trapping-set profiles stored in the RAM memory, each trapping-set profile corresponding to a different trapping set. 19. The apparatus of claim 18, further comprising: a trapping-set-RAM updater adapted to update the RAM memory to store a new trapping-set profile. 20. The apparatus of claim 18, wherein the graph-based code is a Low-Density Parity Check code.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.