Granted Patent B2

US 12,625,765 · App. 18/624,970 · Granted May 12, 2026

Inventors: Chun Xue (Hung Hom, HK); Qiao Li (Xiamen, CN); Tei-Wei Kuo (Kowloon, HK); Min Ye (Shenzhen, CN); Shangyu Wu (Shenzhen, CN); Yufei Cui (Zhuhai, CN)

Assignee: CITY UNIVERSITY OF HONG KONG

G06F11/1068G06F12/0292

Abstract

Claims (46)

1 . A computer-implemented method for encoding data to be stored in a solid-state storage device, comprising the steps of:

a) providing a source data;

b) calculating an entropy of the source data;

c) applying a first encoding scheme to encode the source data into an encoded data, if the entropy is below a threshold; the first encoding scheme adapted to encode most frequently combined characters in the source data into predetermined characters to increase ratio of the predetermined characters in the encoded data; wherein the step of applying a first encoding scheme to encode the source data into an encoded data further comprises:

i. counting frequencies of all combinations of characters, wherein each said combination contains a first number of the characters;

ii. sorting the combinations according to their frequencies;

iii. identifying one said combination that has a highest frequency as the most frequently combined characters;

iv. determining a second number of said combinations, of which said frequencies immediately follow that of the most frequently combined characters; wherein the second number equals to or is smaller than a square of the first number minus one; and

v. encoding the second number of said combinations and the most frequently combined characters into different combinations of the predetermined characters;

d) applying a second data encoding scheme to encode the source data into the encoded data, if the entropy is equal to or higher than the threshold; the second data encoding scheme adapted to encode evenly distributed combined characters into a plurality of patterns with the predetermined characters, in order to increase the ratio of the predetermined characters in the encoded data.

2 . The computer-implemented data encoding method of claim 1 , wherein the first number is two or four.

3 . A computer-implemented data encoding method for encoding data to be stored in a solid-state storage device, comprising the steps of:

a) providing a source data;

b) calculating an entropy of the source data;

c) applying a first encoding scheme to encode the source data into an encoded data, if the entropy is below a threshold; the first encoding scheme adapted to encode most frequently combined characters in the source data into predetermined characters to increase ratio of the predetermined characters in the encoded data; wherein the step of applying a first encoding scheme to encode the source data into an encoded data further comprises:

i. counting frequencies of all combinations of characters, wherein each said combination contains a first number of the characters;

ii. sorting the combinations according to their frequencies;

iii. identifying one said combination that has a highest frequency as the most frequently combined characters;

iv. determining a second number of said combinations, of which said frequencies immediately follow that of the most frequently combined characters; and

v. encoding the second number of said combinations and the most frequently combined characters into different combinations of the predetermined characters;

d) applying a second data encoding scheme to encode the source data into the encoded data, if the entropy is equal to or higher than the threshold; the second data encoding scheme adapted to encode evenly distributed combined characters into a plurality of patterns with said predetermined characters, in order to increase the ratio of the predetermined characters in the encoded data;

wherein Step v) is conducted based on a mapping table, the mapping table created upon a first write request into the solid-state storage drive.

4 . The computer-implemented data encoding method of claim 3 , wherein the mapping table is stored in an out-of-band (OOB) area of a page within a flash memory of the solid-state storage drive.

5 . A computer-implemented data encoding method for encoding data to be stored in a solid-state storage device, comprising the steps of:

a) providing a source data;

b) calculating an entropy of the source data;

c) applying a first encoding scheme to encode the source data into an encoded data, if the entropy is below a threshold; the first encoding scheme adapted to encode most frequently combined characters in the source data into predetermined characters to increase ratio of the predetermined characters in the encoded data; and

d) applying a second data encoding scheme to encode the source data into the encoded data, if the entropy is equal to or higher than the threshold; the second data encoding scheme adapted to encode evenly distributed combined characters into a plurality of patterns with the predetermined characters, in order to increase the ratio of the predetermined characters in the encoded data; wherein the step of applying the second data encoding scheme to encode the source data into the encoded data further comprises:

i) identifying a pair of combinations of characters including a first combination and a second combination, the first combination having more the predetermined characters than the second combination;

ii) encoding the first combination into a first one of the plurality of patterns; and

iii) encoding the second combination into a second one of the plurality of patterns;

wherein the first combination and the second combination each contain a first number of the characters; the first and second ones of the plurality of patterns each containing a second number of the predetermined characters; the first number being smaller than the second number; and

wherein a first number of most significant characters in the first one of the plurality of patterns are identical to a first number of most significant characters in the second one of the plurality of patterns.

6 . The computer-implemented data encoding method of claim 5 , wherein a difference between the first number and the second number is one.

7 . The computer-implemented data encoding method of claim 4 , wherein Step ii) and Step iii) are conducted based on a mapping table, the mapping table being pre-defined prior to Step d).

8 . The computer-implemented data encoding method of claim 5 , wherein the second combination contains none of the predetermined characters, and the first combination consists entirely of the predetermined characters.

9 . The computer-implemented data encoding method of claim 1 , wherein Step b) further comprises conducting integer operations on the source data based on a log lookup table.

10 . The computer-implemented data encoding method of claim 1 , wherein Step b) is performed by an embedded processor in a controller of the solid-state storage device.

11 . The computer-implemented data encoding method of claim 1 , wherein the predetermined characters represent voltage states in the solid-state storage device.

12 . The computer-implemented data encoding method of claim 2 , wherein a number of the predetermined characters is two.

13 . The computer-implemented data encoding method of claim 1 , wherein the first encoding scheme is skewed coding scheme, and the second encoding scheme is reversed Huffman coding.

14 . A non-transitory computer-readable memory recording medium having computer instructions recorded thereon, the computer instructions, when executed on one or more processors, causing the one or more processors to perform operations according to the method according to claim 1 .

15 . A computing system comprising:

a) one or more processors; and

b) memory containing instructions that, when executed by the one or more processors, cause the computing system to perform operations according to the method of claim 1 .

16 . The computing system of claim 15 , further comprising a solid-state storage device controller; said one or more processors being one or more embedded processors in the solid-state storage device controller.

Assignments (1)

Continuity (1)

References Cited (37)