Symbol frequency leveling in a storage system

• US 20040044835A1
• Filed: 08/29/2002
• Published: 03/04/2004
• Est. Priority Date: 08/29/2002
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Corporation (Western Digital Corporation)
• Inventors: Gross, Stephen J., Gongwer, Geoffrey S.
• Granted Patent: US 6,941,412 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: H03M 5/00 Conversion of the form of the representation of individual digits
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

Methods and apparatus for transforming data into a format which may be efficiently stored in a non-volatile memory are disclosed. According to one aspect of the present invention, a method for storing information of a first data format in a memory system includes generating statistics associated with the first data format, and transforming the information from the first data format to a second data format using the statistics. Once the information is transformed into the second data format, the information is stored into a memory. Storing the information in the second data format in the memory includes storing an identifier that identifies a transformation used to transform the information to the second data format. In one embodiment, costs associated with storing the information in the second data format are less than or equal to costs associated with storing the information in the first data format.

Claims

1. A method for storing information in a memory system, the information being in a first data format, the method comprising:

generating statistics associated with the first data format;

transforming the information from the first data format to a second data format using the statistics; and

storing the information in the second data format in a memory associated with the memory system, wherein storing the information in the second data format in the memory includes storing an identifier in the memory which indicates a transformation used to transform the information from the first data format to the second data format.

2. The method of claim 1 wherein the first data format includes at least one occurrence of a first symbol, and generating the statistics associated with the first data format includes:

determining a density of the first symbol in the first data format, wherein determining the density includes determining a numerical value associated with occurrences of the first symbol in the first data format, the numerical value being indicative of the density.

3. The method of claim 2 wherein transforming the information from the first data format to the second data format using the statistics includes:

transforming the information from the first data format to the second data format to reduce the density of the first symbol within the information.

4. The method of claim 1 wherein generating the statistics associated with the first data format includes:

determining a density of a first symbol in the first data format, wherein determining the density includes determining a percentage associated with occurrences of the first symbol in the first data format.

5. The method of claim 4 wherein transforming the information from the first data format to the second data format using the statistics includes:

transforming the information from the first data format to the second data format to increase the density of the first symbol within the information.

6. The method of claim 1 wherein receiving the information in the first data format, on the memory system includes:

receiving the information from a host system, the host system being in communication with the memory system.

7. The method of claim 1 wherein at least one cost associated with storing the information in the second data format is less than or equal to at least one cost associated with storing the information in the first data format.

8. The method of claim 1 wherein power used by the memory system for storing the information in the second data format is less than or equal to power used by the memory system for storing the information in the first data format.

9. A method for retrieving information in a memory system, the information being stored in a first data format in a memory of the memory system, the method comprising:

analyzing the information in the first data format, wherein analyzing the information in the first data format includes determining at least one appropriate transformation for use in transforming the information from the first data format into a second data format; and

transforming the information from the first data format into the second data format using the appropriate transformation.

10. The method of claim 9 wherein the second data format was initially transformed using statistics associated with the second data format.

11. The method of claim 9 wherein analyzing the information in the first data format includes:

reading a section of the information in the first data format, wherein the section includes symbols which identify the appropriate transformation.

12. The method of claim 9 wherein the memory system is in communication with a host system, the method further including:

providing the transformed information in the second data format to the host system.

13. The method of claim 9 wherein at least one cost associated with storing the information in the first data format in the memory is not greater than at least one cost associated with storing the information in the second data format in the memory.

14. The method of claim 9 wherein power used by the memory system for storing the information in the first data format in memory is not greater than power used by the memory system for storing the information in the first data format in the memory.

15. A memory device comprising:

a memory;

an input receiver, the input receiver being arranged to receive information, the information being arranged in a first data format;

a statistics generator, the statistics generator being arranged to generate statistics associated with the first data format; and

a transformer, the transformer being arranged to use the statistics to transform the information from the first data format into a second data format, the transformer being further arranged to store the information in the second data format in the memory.

16. The memory device of claim 15 wherein costs associated with storing the information in the second data format are less than or equal to costs associated with storing the information in the first data format.

17. The memory device of claim 15 wherein the statistics generator is further arranged to determine a density of a first symbol in the first data format by determining a numerical value associated with occurrences of the first symbol in the first data format, the numerical value being indicative of the density.

18. The memory device of claim 17 wherein the transformer is further arranged to transform the information from the first data format to the second data format to reduce the density of the first symbol within the information.

19. The memory device of claim 17 wherein the transformer is further arranged to transform the information from the first data format to the second data format to increase the density of the first symbol within the information.

20. The memory device of claim 17 wherein the transformer is further arranged to store an identifier with the information in the second data format, the identifier being arranged to substantially identify at least one transformation used to transform the information from the first data format into the second data format.

21. The memory device of claim 20 further including an information processor, the information processor being arranged to read the identifier, the information processor further being arranged to cooperate with the transformer such that the transformer identifies at least one appropriate transformation to transform the information from the second data format to the first data format.

22. The memory device of claim 21 wherein the input receiver is arranged to interface with a host system and the transformer is further arranged to provide the information in the first data format to the host system after the transformer transforms the information from the second data format to the first data format.

23. The memory device of claim 15 wherein the input receiver is arranged to interface with a host system to receive the information in the first data format from the host system.

24. The memory device of claim 15 wherein the memory system is a non-volatile memory system that interfaces with a host system.

25. The memory device of claim 24 wherein the non-volatile memory system is removable from the host system.

26. The memory device of claim 24 wherein the memory is a non-volatile storage element.

27. The memory device of claim 24 wherein the memory device is a card selected from the group consisting of a PC card, a CompactFlash card, a MultiMedia card, a secure digital card, a Memory Stick card, and a Smart Media card.

28. The memory device of claim 24 wherein the memory device is a single chip device.

29. A system comprising:

a host system; and

a memory device, the memory device being arranged to interface with the host system to obtain information arranged in a first data format from the host system, the memory device including a memory, a statistics generator, and a transformer, wherein the statistics generator is arranged to generate statistics associated with the first data format and the transformer is arranged to use the statistics to transform the information from the first data format into a second data format, the transformer further being arranged to store the information in the second data format in the memory.

30. The system of claim 29 wherein the statistics generator is further arranged to determine a density of a first symbol in the first data format by determining a percentage associated with occurrences of the first symbol in the first data format.

31. The system of claim 30 wherein the transformer is further arranged to transform the information from the first data format to the second data format to reduce the density of the first symbol within the information.

32. The system of claim 30 wherein the transformer is further arranged to transform the information from the first data format to the second data format to increase the density of the first symbol within the information.

33. The system of claim 29 wherein the transformer is further arranged to store an identifier with the information in the second data format, the identifier being arranged to substantially identify at least one transformation used to transform the information from the first data format into the second data format.

34. The system of claim 33 wherein the memory device further includes an information processor, the information processor being arranged to read the identifier, the information processor further being arranged to cooperate with the transformer such that the transformer identifies at least one appropriate transformation to transform the information from the second data format to the first data format.

35. The system of claim 34 wherein the memory device is arranged to provide the information in the first data format to the host system after the transformer transforms the information from the second data format to the first data format.

36. The system of claim 33 wherein the host system includes an information processor and a second transformer, the information processor being arranged to read the identifier, the information processor further being arranged to cooperate with the second transformer such that the second transformer identifies at least one appropriate transformation to transform the information from the second data format to the first data format.

37. The system of claim 29 wherein the memory system is a non-volatile memory system.

38. The system of claim 37 wherein the non-volatile memory system is removable from the host system.

39. The system of claim 37 wherein the non-volatile memory system is embedded in the host system.

40. The system of claim 37 wherein the memory is a non-volatile storage element.

41. The system of claim 29 wherein the memory device is a card selected from the group consisting of a PC card, a CompactFlash card, a MultiMedia card, a secure digital card, a Memory Stick card, and a Smart Media card.

42. The system of claim 29 wherein the memory device is a single chip device.

43. The system of claim 29 wherein the host system is arranged to capture the information and to provide the information to the memory device in the first format.

44. The system of claim 43 wherein the host system is one selected from the group consisting of a digital camera, a video camera, a cellular telephone, a communications device, an audio player, and a video player.

45. The system of claim 29 wherein the transformer is further arranged to perform an additional transformation on the information, wherein the additional transformation substantially does not use the statistics.

46. A memory device comprising:

means for storing information;

means for receiving input, the means for receiving input being arranged to receive the information, the information being arranged in a first data format;

means for generating statistics, the means for generating statistics being arranged to generate statistics associated with the first data format; and

means for transforming the information, the means for transforming the information being arranged to use the statistics to transform the information from the first data format into a second data format.

47. The memory device of claim 46 wherein the means for transforming the information are further arranged to store the information in the second data format in the means for storing the information.

48. The memory device of claim 46 wherein the means for transforming the information is further arranged to perform an additional transformation, the additional transformation being arranged not to use the statistics.

49. The memory device of claim 46 wherein costs associated with storing the information in the second data format are less than or equal to costs associated with storing the information in the first data format.

50. The memory device of claim 46 wherein power usage amounts associated with storing the information in the second data format are less than or equal to power usage amounts associated with storing the information in the first data format.

51. The memory device of claim 46 wherein the means for generating statistics includes means for determining a density of a first symbol in the first data format by determining a percentage associated with occurrences of the first symbol in the first data format.

52. The memory device of claim 51 wherein the means for transforming the information is further arranged to transform the information from the first data format to the second data format to reduce the density of the first symbol within the information.

53. The memory device of claim 51 wherein the means for transforming the information is further arranged to transform the information from the first data format to the second data format to increase the density of the first symbol within the information.

54. The memory device of claim 46 wherein the means for transforming the information is further arranged to store an identifier associated with the information in the second data format, the identifier being arranged to substantially identify at least one transformation used to transform the information from the first data format into the second data format.

55. The memory device of claim 54 further including means for processing the information, the means for processing the information including means for reading the identifier, the means for processing the information further being arranged to cooperate with the means for transforming the information such that the means for transforming identifies at least one appropriate transformation to transform the information from the second data format to the first data format.

56. The memory device of claim 55 wherein the means for receiving input is arranged to interface with a host system and the means for transforming the information includes means for providing the information in the first data format to the host system after the means for transforming the information transforms the information from the second data format to the first data format.

57. The memory device of claim 54 further including:

means for processing the information, the means for processing the information including means for reading the identifier; and

second means for transforming the information, wherein the means for processing the information is arranged to cooperate with the second means for transforming the information such that the second means for transforming identifies at least one appropriate transformation to transform the information from the second data format to the first data format.

58. The memory device of claim 46 wherein the means for receiving input is arranged to interface with a host system to receive the information in the first data format from the host system.

59. The memory device of claim 46 wherein the memory system is a non-volatile memory system that interfaces with a host system.

60. A method for transforming data from a first format into a second format, the method comprising:

determining a first density of a first symbol, the first density being associated with the first format;

determining a second density of a second symbol, the second density being associated with the first format, wherein the first density is greater than the second density; and

leveling the first symbol with the second symbol, wherein leveling the first symbol with the second symbol includes creating a third density of the first symbol, the third density being associated with the second format, and creating a fourth density of the second symbol, the fourth density being associated with the second format, wherein the third density is not greater than the first density.

61. The method as recited in claim 60 wherein the fourth density is not less than the second density.

62. The method as recited in claim 60 wherein the second format includes an indicator, the indicator being arranged to indicate that the first symbol has been leveled with the second symbol.

63. A method for transforming data from a first format into a second format, the method comprising:

determining a first density of a first symbol, the first density being associated with the first format;

determining a second density of a second symbol, the second density being associated with the first format, wherein the first density is not less than the second density; and

leveling the first symbol with the second symbol, wherein leveling the first symbol with the second symbol includes creating a third density of the first symbol, the third density being associated with the second format, and creating a fourth density of the second symbol, the fourth density being associated with the second format, wherein the fourth density is not less than the second density.

64. The method as recited in claim 63 wherein the third density is not greater than the first density.

65. The method as recited in claim 63 wherein the second format includes an indicator, the indicator being arranged to indicate that the first symbol has been leveled with the second symbol.