Codec with genetic adaptation

• US 6,539,366 B1
• Filed: 04/30/1998
• Issued: 03/25/2003
• Est. Priority Date: 04/30/1998
• Status: Expired due to Term

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Intel Corporation
• Inventors: Doyle, Patrick F., Aktan, Burcin
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/071,049
• Time in Patent Office: 1,790 Days
• Field of Search: 706/13, 382/224, 382/9
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A codec to compress information by generating a set of basis vectors based upon a population of vectors according to a pseudo-random sequence; and encoding the information into a set of coefficients indicative of a projection of the information onto the linear span of the set of basis vectors provided the projection satisfies a criterion of goodness. The generation of the basis vectors is based upon a genetic algorithm. To decode, the information is reconstructed or uncompressed by summing the set of basis vectors weighted by the set of coefficients.

Claims

1. A storage device comprising a computer readable medium, wherein the computer readable medium has stored therein instructions to cause a computer system to perform a method, the method comprising:

generating a set of basis vectors based upon a population of vectors according to at least one pseudo-random sequence; and

encoding an information vector into a set of coefficients indicative of an orthogonal projection of the information vector onto the linear span of the set of basis vectors provided the orthogonal projection satisfies a criterion of goodness.

2. The storage device as set forth in claim 1, the method further comprising updating the population of vectors with the set of basis vectors if the orthogonal projection does not satisfy the criterion of goodness.

3. The storage device as set forth in claim 2, the method further comprising reconstructing a decoded information vector based upon the set of coefficients and the set of basis vectors.

4. The storage device as set forth in claim 1, the method further comprising reconstructing a decoded information vector based upon the set of coefficients and the set of basis vectors.

5. The storage device as set forth in claim 1, wherein the population of vectors comprises a plurality of sets of vectors, each set of vectors belonging to the population of vectors defining a parent.

6. The storage device as set forth in claim 5, wherein in generating the set of basis vectors, each basis vector is derived from two parents.

7. The storage device as set forth in claim 6, the method further comprising updating the population of vectors with the set of basis vectors if the orthogonal projection does not satisfy the criterion of goodness.

8. The storage device as set forth in claim 7, the method further comprising reconstructing a decoded information vector based upon the set of coefficients and the set of basis vectors.

9. The storage device as set forth in claim 6, the method further comprising reconstructing a decoded information vector based upon the set of coefficients and the set of basis vectors.

10. The storage device as set forth in claim 6, wherein each parent comprises:

a trait vector;

a dominant vector;

a first genetic vector; and

a second genetic vector.

11. The storage device as set forth in claim 10, wherein in generating the set of basis vectors the method further comprises:

generating a set of vectors derived from a first parent and a second parent to define a child, the child comprising a trait vector, a dominant vector, a first genetic vector, and a second genetic vector;

wherein;

the first genetic vector of the child is derived from the first and second genetic vectors of the first parent according to the at least one pseudo-random sequence;

the second genetic vector of the child is derived from the first and second genetic vectors of the second parent according to the at least one pseudo-random sequence;

the dominant genetic vector of the child is derived from the dominant genetic vectors of the first and second parents according to the at least one pseudo-random sequence;

components of the trait vector of the child are set equal to corresponding components of the first genetic vector of the child if corresponding components of the first and second genetic vectors of the child are equal to each other; and

components of the trait vector of the child are set equal to corresponding components of the dominant vector of the child if corresponding components of the first and second genetic vectors of the child are not equal to each other;

wherein the trait vector of the child belongs to the set of basis vectors.

12. The storage device as set forth in claim 11, the method further comprising updating the population of vectors with the set of basis vectors if the orthogonal projection does not satisfy the criterion of goodness.

13. The storage device as set forth in claim 12, the method further comprising reconstructing a decoded information vector based upon the set of coefficients and the set of basis vectors.

14. The storage device as set forth in claim 11, the method further comprising reconstructing a decoded information vector based upon the set of coefficients and the set of basis vectors.

15. A storage device comprising a computer readable medium, wherein the computer readable medium has stored therein instructions to cause a computer system to perform a method, the method comprising:

generating a set of basis vectors based upon a population of vectors according to at least one pseudo-random sequence; and

projecting orthogonally an information vector onto the linear span of the set of basis vectors.

16. The storage device as set forth in claim 15, the method further comprising updating the population of vectors with the set of basis vectors if the orthogonal projection of the information vector does not satisfy a criterion of goodness.

17. The storage device as set forth in claim 16, the method further comprising reconstructing a decoded information vector based upon the orthogonal projection of the information vector.

18. The storage device as set forth in claim 15, the method further comprising reconstructing a decoded information vector based upon the orthogonal projection of the information vector.

19. The storage device as set forth in claim 15, wherein the population of vectors comprises a plurality of sets of vectors, each set of vectors belonging to the population of vectors defining a parent.

20. The storage device as set forth in claim 19, wherein in generating the set of basis vectors, each basis vector is derived from two parents.

21. The storage device as set forth in claim 20, the method further comprising updating the population of vectors with the set of basis vectors if the orthogonal projection does not satisfy a criterion of goodness.

22. The storage device as set forth in claim 21, the method further comprising reconstructing a decoded information vector based upon the orthogonal projection of the information vector.

23. The storage device as set forth in claim 20, the method further comprising reconstructing a decoded information vector based upon the orthogonal projection of the information vector.

24. The storage device as set forth in claim 20, wherein each parent comprises:

a trait vector;

a dominant vector;

a first genetic vector; and

a second genetic vector.

25. The storage device as set forth in claim 24, wherein in generating the set of basis vectors the method further comprises:

generating a set of vectors derived from a first parent and a second parent to define a child, the child comprising a trait vector, a dominant vector, a first genetic vector, and a second genetic vector;

wherein;

the first genetic vector of the child is derived from the first and second genetic vectors of the first parent according to the at least one pseudo-random sequence;

the second genetic vector of the child is derived from the first and second genetic vectors of the second parent according to the at least one pseudo-random sequence;

the dominant genetic vector of the child is derived from the dominant genetic vectors of the first and second parents according to the at least one pseudo-random sequence;

components of the trait vector of the child are set equal to corresponding components of the first genetic vector of the child if corresponding components of the first and second genetic vectors of the child are equal to each other; and

components of the trait vector of the child are set equal to corresponding components of the dominant vector of the child if corresponding components of the first and second genetic vectors of the child are not equal to each other;

wherein the trait vector of the child belongs to the set of basis vectors.

26. The storage device as set forth in claim 25, the method further comprising updating the population of vectors with the set of basis vectors if the orthogonal projection does not satisfy a criterion of goodness.

27. The storage device as set forth in claim 26, the method further comprising reconstructing a decoded information vector based upon the orthogonal projection of the information vector.

28. The storage device as set forth in claim 25, the method further comprising reconstructing a decoded information vector based upon the orthogonal projection of the information vector.

29. A storage device with a program code stored therein to program a computer system to perform a method, the method comprising:

generating a set of basis vectors based upon a population of vectors according to at least one pseudo-random sequence;

receiving a set of coefficients; and

generating a reconstructed information vector by summing the set of basis vectors weighted by the set of coefficients.

30. The storage device as set forth in claim 29, wherein the population of vectors comprises a plurality of sets of vectors, each set of vectors belonging to the population of vectors defining a parent.

31. The storage device as set forth in claim 30, wherein in generating the set of basis vectors, each basis vector is derived from two parents.

32. The storage device as set forth in claim 31, wherein each parent comprises:

a trait vector,

a dominant vector;

a first genetic vector; and

a second genetic vector.

33. The storage device as set forth in claim 32, wherein in generating the set of basis vectors the method further comprises:

generating a set of vectors derived from a first parent and a second parent to define a child, the child comprising a trait vector, a dominant vector, a first genetic vector, and a second genetic vector;

wherein;

the first genetic vector of the child is derived from the first and second genetic vectors of the first parent according to the at least one pseudo-random sequence;

the second genetic vector of the child is derived from the first and second genetic vectors of the second parent according to the at least one pseudo-random sequence;

the dominant genetic vector of the child is derived from the dominant genetic vectors of the first and second parents according to the at least one pseudo-random sequence;

components of the trait vector of the child are set equal to corresponding components of the first genetic vector of the child if corresponding components of the first and second genetic vectors of the child are equal to each other; and

components of the trait vector of the child are set equal to corresponding components of the dominant vector of the child if corresponding components of the first and second genetic vectors of the child are not equal to each other;

wherein the trait vector of the child belongs to the set of basis vectors.

34. A method for encoding and decoding a signal represented by an information vector, the method comprising:

generating a set of basis vectors based upon a population of vectors according to at least one pseudo-random sequence;

encoding the signal into a set of coefficients indicative of an orthogonal projection of the information vector onto the linear span of the set of basis vectors; and

decoding the signal by summing the set of basis vectors weighted by the set of coefficients.

35. The method as set forth in claim 34, wherein the population of vectors comprises a plurality of sets of vectors, each set of vectors belonging to the population of vectors defining a parent;

wherein in generating the set of basis vectors, each basis vector is derived from two parents.

36. The method as set forth in claim 35, wherein each parent comprises:

a trait vector;

a dominant vector;

a first genetic vector; and

a second genetic vector;

wherein in generating the set of basis vectors the method further comprises;

generating a set of vectors derived from a first parent and a second parent to define a child, the child comprising a trait vector, a dominant vector, a first genetic vector, and a second genetic vector;

wherein;

the first genetic vector of the child is derived from the first and second genetic vectors of the first parent according to the at least one pseudo-random sequence;

the second genetic vector of the child is derived from the first and second genetic vectors of the second parent according to the at least one pseudo-random sequence;

the dominant genetic vector of the child is derived from the dominant genetic vectors of the first and second parents according to the at least one pseudo-random sequence;

components of the trait vector of the child are set equal to corresponding components of the first genetic vector of the child if corresponding components of the first and second genetic vectors of the child are equal to each other; and

components of the trait vector of the child are set equal to corresponding components of the dominant vector of the child if corresponding components of the first and second genetic vectors of the child are not equal to each other;

wherein the trait vector of the child belongs to the set of basis vectors.