Abstraction and de-abstraction of a digital data stream

• US 10,148,285 B1
• Filed: 11/15/2012
• Issued: 12/04/2018
• Est. Priority Date: 07/25/2012
• Status: Active Grant

• Current Assignee: Erich Schmitt
• Original Assignee: Erich Schmitt
• Inventors: Schmitt, Erich
• Primary Examiner(s): Mai, Lam T
• Application Number:
  US13/677,477
• Time in Patent Office: 2,210 Days
• Field of Search: 341 50- 90, 717104, 717116, 717117, 717126, 717136, 717139, 717142, 717159, 717108, 709203
• CPC Class Codes: H03M 7/14 Conversion to or from non-weighted codes
• CPC Class Codes: H03M 7/3059 Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression
• CPC Class Codes: H03M 7/55 Compression Theory, e.g. compression of random number, repeated compression

Abstract

Techniques for abstracting a set of abstraction codes from an input bit string and for de-abstracting to recover an original input bit string from a set of abstraction codes and a string length are described. Applications of these techniques to compressing, storage, networking, encryption are also described as is a parallel configuration for abstraction and de-abstraction.

Claims

1. A device implemented method comprises:

receiving by a computing device that includes a processor and memory, an input bit string of bits, with the input bit string having a finite number of bits, the input bit string having a bit length L;

iteratively transforming by the computing device, the bits of the input string into sets of interim function codes, with for each bit of the input bit string each of the sets of the interim function codes transformed in part from functions that are reverse sequence isomoric pairs and previous determined ones of the interim function codes; and

providing by the computing device, the set of the interim function codes that is determined for the bit at the bit position L of the input bit string, as a set of abstraction codes that correspond to a lossless representation of the input bit string having fewer bits than the bit length L.

2. The device implemented method of claim 1 wherein iteratively transforming, transforms the bits of the input bit string further from beginning conditions for the bit position corresponding to the corresponding input bits, and permissibility conditions;

and the method further comprises;

applying a permutation of a bit representation for the function codes to the abstraction codes.

3. The device implemented method of claim 1 wherein the set of abstraction codes and the length L of the input bit string are the representation of the input bit string, and wherein the input bit string is a digital bit string that represents either digital data or computer instruction code.

4. The device implemented method of claim 1 wherein the set of abstraction codes are two abstraction codes with each abstraction code being six bits in length.

5. The device implemented method of claim 1 wherein the set of abstraction codes are two abstraction codes with each abstraction code being five bits in length.

6. The device implemented method of claim 1 wherein the set of abstraction codes are two abstraction codes with each abstraction code being four bits in length.

7. The device implemented method of claim 1 wherein iteratively transforming, further comprises:

iteratively accessing by the computing device a table structure stored in the memory to determine the set of interim function codes, for each iteration, retrieving from the table structure the set of interim function codes for a bit position, according to beginning conditions for the bit position and values of the determined set of the interim function codes for a present set of inputs and a next set of inputs.

8. The device implemented method of claim 1 further comprising:

iteratively retrieving the interim function codes from a table by evaluating for each bit of the input bit string, a corresponding set of present inputs and initial state for the bit of the input bit string to provide a subsequent set of functions and next set of inputs for a next bit in the input string.

9. The device implemented method of claim 1 wherein interactively transforming the bits of the input string into the sets of interim function codes further comprises:

iteratively determining a DA bit for each bit position of the input bit string, according to beginning conditions and by;

testing for a limit condition at the bit positions;

when a limit condition is not encountered, using the bit from the input bit string at the bit position as the DA bit value of a next set inputs; and

when a limit condition is encountered, substituting for the bit from the input bit string at the bit position, a limit bit from a limit bit table according to an index value of the limit string, for the bit at the bit position of the input bit string as the DA bit value of the next set of inputs.

10. The device implemented method of claim 9 wherein testing for the limit condition further comprises determining by the device at the bit positions whether for a value of an AD bit of an AD bit string at the bit positions, the limit condition occurs when for a present input of the AD bit or the DA bit, the interim function codes have the same values for either the AD and/or the DA bits.

27. The device implemented method of claim 1 wherein the memory stores a table accessible by a computer program product executed by the processor to:

perform the iteratively determining with the table including plural rows, with each row representing a function.

28. The device implemented method of claim 1 wherein the memory stores:

a first table for a first, function type accessible by a computer program product executed by the processor to perform the iteratively determining with the table including plural rows, with each row representing a function and with each row including

a set of present inputs, including a state value, an AD value and a DA value; and

a next set of present inputs including a set of transition values for each transition level of the function; and

a second table for a second different function type, the second table further comprising;

plural rows, with each row representing a function of the second function type and with each row including columns that include

a set of present inputs, including a state value, an AD value and a DA value; and

a next set of present inputs including a set of transition values for each transition level of the second function type.

29. The device implemented method of claim 27 wherein the function is a first function type and a second, different function type and with the first and second function types represented by the plural rows of the table and the columns including:

a set of present inputs, including a state value, an AD value and a DA value; and

a next set of present inputs including a set of transition values for each transition level of corresponding ones of the first and second function types.

30. The device implemented method of claim 27 wherein the table includes rows that have permissible and non-permissible values for the function.

31. The device implemented method of claim 27 wherein the table includes only rows that have permissible values for the function.

32. The device implemented method of claim 27 wherein the table includes rows that have permissible and non-permissible values for at least one of the first and second function types.

33. The device implemented method of claim 28 wherein the table includes only rows that have permissible values for the first and second function types.

34. The device implemented method of claim 29 wherein the table includes rows that have permissible and non-permissible values for at least one of the first and second function types.

35. The device implemented method of claim 29 wherein the table includes only rows that have permissible values for the first and second function types.

41. The device implemented method of claim 1 wherein the set of abstraction codes are two codes with each code being four bits in length.

91. The device implemented method of claim 2 wherein calculating by the device the set of abstraction codes accesses a table that stores functions based on a non-abelian group of order six.

11. A device implemented method of producing a representation of an input bit string of a finite number of digital bits of a length L, the representation having fewer bits than the finite number of bits L, the method comprises:

receiving by the device that includes a processor and memory, the input bit string of the length L;

iteratively, determining by the device a set of interim function codes for each bit of the input bit string, up to the length L of the input bit string by iterative accesses to a table that stores function codes according to beginning conditions, final states and permissibility conditions; and

when the length L of the input bit string has been reached by the iterative determining, producing a final set of interim function codes.

12. The device implemented method of claim 11 wherein the table is included in a program that executes on the processor to perform the method on the device, and the method further comprises:

detecting a non-permissible condition;

determining by the device a bit value to substitute for a bit value in the input string based on the detected non-permissible condition; and

obtaining by the device for each bit in the input string including any substituted bit values, interim values of the set of interim functions from a table stored in the memory, with the table storing beginning condition values including present state values, the interim function codes, and next present state values of the interim function codes.

13. The device implemented method of claim 11 wherein the input string is of blocks of the length L and iteratively determining further comprises:

iteratively, determining by the device the interim function codes over each of the blocks of the length L of the input string;

transforming the final set of interim function codes into a pair of transformed abstraction codes by;

selecting a permutation of a binary representation of function codes as a binary representation to correspond to the final set of the interim function codes.

14. The device implemented method of claim 11 wherein the final set of interim function codes are a pair of abstraction codes that is the representation of the input string, with each of the pair provided as one of binary representations that are each four bits in length or that are each five bits in length or that are each six bits in length.

15. The device implemented method of claim 11 wherein the input bit string distributed over plural blocks of known size to accommodate the finite number of bits of the length L, and iteratively determining further comprises:

iteratively, determining by the device the interim functions for each of the blocks in succession.

16. The device implemented method of claim 11 further comprising:

iteratively determining by the device the interim and the final set of functions by evaluating each bit of the input bit string according to a set of initial state values to provide subsequent interim function values and next state values.

17. The device implemented method of claim 11 further comprising:

retrieving by the device a limit bit from a table of limit bits, when a non-permissive condition is encountered, where the number of bits in the limit bit table is indexed from an initial index to a value of at least about L/3.

18. The device implemented method of claim 11 wherein iteratively calculating interim functions further comprises:

iteratively determining by the device a DA bit for bit positions of the input bit string, by;

testing for a permissive condition for each of the bit positions to determine presence of a limit condition;

when the limit condition is not encountered, using the bit from the input bit string according to the bit position; and

when the limit condition is encountered, substituting for the bit from the input bit string according to the bit position, a limit bit from a limit bit table according to an index value of the limit string.

19. The device implemented method of claim 18 wherein a limit condition occurs when for a present set of inputs that comprise bits of an AD bit string and bits of a DA bit string, the computed interim functions have the same values for either the AD and/or the DA input bits.

20. The device implemented method of claim 19 wherein the input bit string has an index k and iteratively determining operates over the index k, and the method further comprises:

determining by the device when iteratively determining reaches the index value of k equal to the length L of the input bit string; and

when k equals the length L, the iterative determining provides the final set of interim functions.

21. The device implemented method of claim 11 wherein an abstraction engine performs the iteratively determining, with the abstraction engine being one of a plurality of abstraction engines, and the input string is one of a parallel set of plural input strings that corresponds to a bit width of a source of the parallel set of plural input strings, and with the method further comprising:

receiving by the plurality of abstraction engines the parallel set of plural input bit strings; and

assigning the abstraction engines to perform the iteratively processing for corresponding ones of the plurality of the input bit strings in the parallel set of plural input bit strings according to input string bit positions to produce corresponding plural abstraction codes per input bit string position.

22. The device implemented method of claim 11 further comprising:

storing in memory in the device a table, and wherein the table comprises;

plural rows, with each row representing a function and with each row including;

a set of present inputs, including a state value, an AD value and a DA value; and

a next set of present inputs including a set of transition values for each transition level of the function.

23. The device implemented method of claim 11 further comprises:

generating a table by the device;

storing the table as a data structure in memory, the table including plural rows, with each row representing a function and with each row including

a set of present inputs, including a state value, an AD value and a DA value; and

a next set of present inputs including a set of transition values for each transition level of the function.

24. The device implemented method of claim 11 further comprising:

determining the length L of the input bit string.

25. The device implemented method of claim 11 wherein the length L of the input bit string is received.

26. The device implemented method of claim 11 wherein the length L of the input bit string is fixed.

92. The device implemented method of claim 11 wherein iteratively calculating by the device the set of abstraction codes accesses a table that stores functions based on a non-abelian group of order six to obtain a subsequent set of functions.

36. A device comprises:

a processor;

memory in communication with the processor, and logic to configure the processor to;

receive an input bit string having a finite number of bits of a bit length L;

iteratively determine plural sets of first and second function codes from the input bit string over the length L of the input bit string for each input bit at each corresponding bit position by calculating each of the plural sets of the first and second function codes from corresponding beginning conditions, permissibility conditions, corresponding next state conditions, and values of the input bit; and

provide the first and second function codes determined for bit position L of the input string, as a representation of the input bit string, where the number of bits in the representation are less than the number of bits in the input bit string.

93. The device of claim 36 wherein the device calculates the abstraction codes by accessing a table that stores interim function codes that are based on a non-abelian group of order six.

37. A computer program product tangibly stored in a non-transitory readable medium hardware storage device that is readable by a computer, the computer program product for producing a representation of an input bit string of bits of a finite length L, the representation having fewer bits than the finite number of bits L, the computer program product comprising instructions for causing a processor to:

receive an input bit string having a finite number of data bits of a bit length L;

iteratively determine plural sets of interim function codes from the input bit string over the length L of the input bit string by calculating each of the sets of interim function codes from corresponding beginning conditions for a corresponding bit position of the input bit stream, permissibility conditions, next state conditions, and data bits of the input string or substituted data bits from a limit string; and

provide the set of interim function codes determined for bit position L of the input string as a representation of the input bit string.

94. The computer program product of claim 37 wherein the processor calculates the abstraction codes by accessing a table that stores interim function codes that are based on a non-abelian group of order six.

38. A electronic device implemented method comprises:

receiving by the electronic device, an input bit string of bits of a finite length of a length L;

producing by the electronic device a set of abstraction codes by an abstraction engine in communication with the electronic storage device, by iteratively transforming the bits of the input string into sets of interim function codes, with for each bit of the input bit string each of the sets of the interim function codes transformed in part from functions that are reverse sequence isomoric pairs, and previous determined ones of the interim function codes with the set of abstraction codes being the set of interim function codes that were transformed a bit position corresponding to the length L of the input string; and

storing by the electronic device, the set of abstraction codes into a data storage medium of the electronic storage device, with the set of codes corresponding to an abstracted representation of the input bit string.

39. The device implemented method of claim 38 wherein the set of abstraction codes are two codes with each code being six bits in length.

40. The device implemented method of claim 38 wherein the set of abstraction codes are two codes with each code being five bits in length.

42. The device implemented method of claim 38 wherein the data storage medium of the storage device is selected from the group consisting of an optical medium, a magnetic medium, and a semiconductor medium.

43. The device implemented method of claim 38 wherein the abstraction engine is provided in the storage device and is configured to produce the abstraction codes by:

iteratively determining by the abstraction engine according to permissibility conditions, sets of interim function codes, with for each iteration for a given bit of the input bit string, evaluating a corresponding set of present inputs and initial state to provide an first interim set of function codes and a next set of inputs and a next state for a next bit in the input string, when the bit at the length L of the input bit string has been evaluated, producing a final set of function codes; and

transforming by the abstraction engine the final set of function codes into the abstraction codes.

44. The device implemented method of claim 38 wherein the length L of the input bit string is a known length.

45. The device implemented method of claim 38 wherein the length L of the input bit string is determined by populating one or more structures each of a known length with the input bit string by the abstraction engine.

46. The device implemented method of claim 43 wherein determining permissibility conditions comprises:

determining when a limit condition occurs.

47. The device implemented method of claim 38 wherein the input bit string has an index k, the method further comprising:

iteratively calculating by the abstraction engine sets of interim function codes for values at bit positions of the input string;

testing for an impermissibility condition by detecting that one or both of values for DA and AD conditions result in the same interim function code;

determining when the index k reaches the length L of the input bit string; and

when k has reached the length L,

outputting final values of the interim function codes; and

transforming the final values of the computed interim function codes into the abstraction codes.

87. The device implemented method of claim 46 wherein when a limit condition occurs, the device substitutes for the data bit from the input bit string according to the bit position, a limit bit from a limit bit table according to an index value of the limit string.

88. The device implemented method of claim 46 wherein when a limit condition is not present the device uses the data bit from the input bit string according to the bit position.

95. The device implemented method of claim 43 wherein obtaining interim values comprises:

retrieving subsequent sets of functions from the table that stores interim function codes that are and that is based on a non-abelian group of order six.

48. A storage device comprises:

an interface configured to receive an input bit string of data bits of a finite length L;

a storage medium; and

an abstraction engine configured to;

receive the input bit string; and

produce from the input bit string a set of abstraction codes, where the set of abstraction codes comprise a first code having a first length of a number of bits, and a second code having the same first length of the number of bits;

circuitry to send the set of abstraction codes to the storage medium to store the set of codes in a location in the storage medium, with the first and second codes corresponding to an abstracted lossless representation of the input bit string.

96. The device of claim 48 wherein the device produces the abstraction codes by applying a table that stores interim function codes that are based on a non-abelian group of order six.

49. A device implemented method of transmitting data over a network, the method comprises:

receiving by a device an input bit string of data bits of a finite length defined as a length L;

producing from the input bit string by an abstraction engine in the device a set of abstraction codes that represent the input bit string;

forming a formatted unit of data comprising connection information and a payload with the payload comprising the set of abstraction codes that represent the input bit string.

50. The device implemented method of claim 49 wherein the set of abstraction codes are two abstraction codes with each code being six bits in length.

51. The device implemented method of claim 49 wherein the set of abstraction codes are two abstraction codes with each code being five bits in length.

52. The device implemented method of claim 49 wherein the set of abstraction codes are two abstraction codes with each code being four bits in length.

53. The device implemented method of claim 49, wherein the length L of the input bit string is a known length and the payload is a fixed length.

54. The device implemented method of claim 53 wherein the abstraction engine is configured for:

iteratively determining by the abstraction engine a set of interim function codes, for a given bit of the input bit string, evaluating a corresponding set of present inputs and initial state to provide an interim set of function codes and a next set of inputs and next state, for a next bit in the input string, according to permissibility conditions; and

when the length of the input bit string has been reached producing a final set of function codes; and

transforming by the abstraction engine the final set of function codes into the abstraction codes that are used to form the payload of the formatted unit of data.

55. The device implemented method of claim 49 further comprising:

determining the length L of the input bit string.

56. The device implemented method of claim 49 further comprising:

receiving the length L of the input bit string.

57. The device implemented method of claim 54 wherein determining permissibility conditions comprises

determining when a limit condition occurs by detecting an impermissibility condition when one or both of values for DA and AD conditions result in the same interim function code;

upon detecting an impermissibility condition, using as a value of the DA or AD conditions a bit value obtained from a limit string of predetermined values.

58. The device implemented method of claim 57 wherein the input bit string has an index k, the method further comprises:

determining by the abstraction engine when the index k reaches the length L of the input bit string; and

when k has reached the length L,

outputting by the abstraction engine final values of the computed function codes.

89. The device implemented method of claim 57 wherein when a limit condition occurs, the device substitutes for the data bit from the input bit string according to the bit position, a limit bit from a limit bit table according to an index value of the limit string.

90. The device implemented method of claim 57 wherein when a limit condition is not present the device uses the data bit from the input bit string according to the bit position.

97. The device implemented method of claim 49 wherein the processor produces the abstraction codes by applying a table that stores interim function codes that are based on a non-abelian group of order six.

98. The device implemented method of claim 54 wherein producing comprises:

retrieving the set of functions from a table that stores interim function codes that are based on a non-abelian group of order six.

59. A network device comprises:

an interface configured to receive an input bit string of data bits of a finite length L;

an abstraction engine configured to;

produce from the input bit string a set of abstraction codes; and

a forming engine that produces a formatted unit of data comprising connection information and a payload, with the payload comprising the set of abstraction codes.

60. The device of claim 59 further comprising:

a storage device that stores the set of abstraction codes, with the set of abstraction codes corresponding to a lossless compressed representation of the input bit string, with the forming engine configured to retrieve the set of abstraction codes from the storage device.

61. The device of claim 59 wherein the formatted unit of data is a fixed length cell.

62. The device of claim 59 wherein the formatted unit of data is a packet.

63. The device of claim 59 wherein the formatted unit of data is a frame.

99. The network device of claim 59 wherein the engine produces the abstraction codes by applying a table that stores interim function codes that are based on a non-abelian group of order six.

64. A device implemented method of encrypting an input bit string of data bits of a finite length into a compressed, encrypted representation of the input bit string, the method comprises:

receiving by a device the input bit string of data bits of finite length defined as length L;

abstracting the input bit string by an abstraction engine into a set of abstraction codes that correspond to a lossless representation of the input bit string, with the abstraction codes formed using a secured abstraction encryption key; and

sending by the device the set of abstraction codes to a recipient application, the set of abstraction codes.

65. The device implemented method of claim 64 wherein the set of abstraction codes are two codes with each code being six bits in length.

66. The device implemented method of claim 64 wherein the set of abstraction codes are two codes with each code being five bits in length.

67. The device implemented method of claim 64 wherein the set of abstraction codes are two codes with each code being four bits in length.

68. The device implemented method of claim 64 wherein the secured abstraction encryption key comprises one or more of a secured instance of a limit string, a secured instance of an address string, and a secured instance of a permutation of a binary representation for the abstraction codes for code transformation by the abstraction engine.

69. The device implemented method of claim 64, further comprising:

exchanging the secured abstraction encryption key with the recipient application in a secure manner.

70. The device implemented method of claim 64 wherein the determined encryption key is a randomly selected permutation of a binary representation of abstraction codes;

and the method further comprises;

transforming by the abstraction engine the abstraction codes into a binary representation using the randomly selected permutation; and

securing exchanging information about the randomly selected permutation with a recipient device including a second abstraction engine.

71. The device implemented method of claim 64 wherein determining the encryption key further comprises:

producing at least one of a random limit string, a random address string and a random permutation for code transformation;

securing the produced at least one as the encryption key.

72. The device implemented method of claim 64 wherein forming from the abstraction the encryption key further comprises:

producing a random permutation for code transformation;

securing the produced random permutation as the encryption key.

73. The device implemented method of claim 72 wherein securing the produced random permutation as the encryption key comprises:

encrypting the encryption key with a different encryption algorithm.

74. The device implemented method of claim 64 further comprising:

sending a value representing the length L of the input bit string to the recipient application.

75. The device implemented method of claim 64 wherein the abstraction engine is configured for:

iteratively determining by the abstraction engine according to permissibility conditions sets of interim function codes, for each iteration for a given bit of the input bit string, evaluating a corresponding set of present inputs and initial state to provide an interim set of function codes and next set of inputs and next state for a next bit in the input string;

when the bit at the length L of the input bit string has been evaluated, producing a final set of function codes; and

transforming by the engine the final set of function codes into the abstraction codes.

76. The device implemented method of claim 70, further comprising:

enabling user selection of at least one of limit string, address string and permutation of a code transformation from which the abstraction engine produces the encryption key.

100. The device implemented method of claim 75 wherein calculating interim function codes comprises:

retrieving the set of functions from a table that stores interim function codes that are based on a non-abelian group of order six.

77. A device implemented method of producing a hash, the method comprises:

receiving a key that corresponds to a stored input bit string of data bits of a finite length L;

producing by an abstraction engine in the device a set of end words by abstracting a set of code words from the input bit string corresponding to the key;

applying by the device the set of end words to point to a location in memory associated with the key.

78. The device implemented method of claim 77 wherein the set of codes are two codes with each code being six bits in length.

79. The device implemented method of claim 77 wherein the set of codes are two codes with each code being five bits in length.

80. The device implemented method of claim 77 wherein the set of codes are two codes with each code being four bits in length.

81. The device implemented method of claim 77, further comprising:

applying the key through the abstraction engine to produce the end words according to;

i end-0 #F3,4 and #G3,4 each containing 4 bits=8 bits=order 0-7,

i end-1,#F3,4 and #G3,4 each containing 4 bits=8 bits=order 8-15,

i end-2,#F3,4 and #G3,4 each containing 4 bits=8 bits=order 16-23,

i end-3,#F3,4 and #G3,4 each containing 4 bits=8 bits=order 24-31; and

storing the end words in storage.

82. The device implemented method of claim 77 further comprising:

iteratively producing by the abstraction engine, a set of abstraction codes.

83. The device implemented method of claim 77 wherein the end words are values used as addresses to memory for data sections correspondingly pointed to by the key.

84. The device implemented method of claim 77 wherein the abstraction engine provides the end words as hashes that map the keys to an index.

85. A device implemented method of producing a cryptographic hash, the method comprises:

providing to a device an input bit string of data bits having a finite length;

calculating by the device from the input bit string a set of abstraction codes; and

returning by the device the set of abstraction codes as the cryptographic hash.

86. A device configuration for abstraction comprises:

a storage device having storage for one or more entries where the one or more entries are data units comprising plural bits in a like plurality of bit positions; and

a like plurality of abstraction units fed by the storage device with each bit position of the storage device coupled to a corresponding one of abstraction engines, with the abstraction engines configured to produce plural abstraction codes according to the corresponding bit position of the storage device coupled to the corresponding abstraction engine.