Method and apparatus for fractal-excited linear predictive coding of digital signals

• US 5,822,721 A
• Filed: 12/22/1995
• Issued: 10/13/1998
• Est. Priority Date: 12/22/1995
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Iterated Systems Inc (Hewlett-Packard Enterprise Company)
• Inventors: Johnson, Steven A., Wu, Sing-Wai
• Primary Examiner(s): Hudspeth, David R.
• Assistant Examiner(s): Smits, Talivaldis Ivars
• Application Number:
  US08/577,540
• Time in Patent Office: 1,026 Days
• Field of Search: 395/2.1, 395/2.12, 395/2.28, 382/249, 704/201, 704/203, 704/219, 704/262, 341/75
• US Class Current: 704/219
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: G10L 19/08 Determination or coding of the excitation function; Determination or coding of the long-term prediction parameters
• CPC Class Codes: G10L 19/12 the excitation function being a code excitation, e.g. in code excited linear prediction [CELP] vocoders
• CPC Class Codes: G10L 25/36 using chaos theory

Abstract

A method for encoding and decoding digital signals, particularly speech signals, by separating the original signal into a linear and nonlinear portions, the nonlinear portion may have linear aspects. The linear portion is encoded by LPC techniques and the nonlinear portion is encoded by use of a fractal transform. The encoded signal consists of LPC filter coefficients and fractal transform coefficients. The encoded signal is decoded by separating the LPC coefficients and fractal coefficients, using the LPC coefficients to generate an LPC filter, decoding the fractal coefficients using a fractal transform decoding method to obtain an error signal, and exciting the LPC filter with the decoded error signal to obtain decoded digital signals.

Claims

1. A method for encoding a digital signal, comprising the steps of:

receiving a digital signal;

encoding the received digital signal using LPC methods to separate and encode a linear portion of the received digital signal;

to obtain a set of prediction filter coefficients;

encoding a residual portion of the received digital signal using a fractal transformation procedure to obtain an encoded error signal; and

supplying the prediction filter coefficients and the encoded error signal as an encoded digital signal.

2. A method as recited in claim 1 wherein the residual portion of the digital signal comprises a LPC residual signal.

3. A method for encoding a digital speech signal, comprising the steps performed by a data processor of:

receiving a digital speech signal;

generating a plurality of frames from the received digital speech signal;

performing a linear predictive code analysis on the frames to determine corresponding prediction filter coefficients;

comparing a speech signal based on the prediction filter coefficients with the received digital speech signal to create an error signal;

dividing the error signal into nonoverlapping subframes;

creating a plurality of range segments for the nonoverlapping subframes, where each range segment is represented by a fractal transformation procedure;

selecting, for the nonoverlapping subframes, the range segment which most closely corresponds to the nonoverlapping subframe; and

representing the digital input as the prediction filter coefficients and the corresponding fractal transformation procedure.

4. A method as recited in claim 3 wherein the step of creating a plurality of range segments comprises using the nonoverlapping subframes.

5. A method as recited in claim 4 wherein the step of creating a plurality of range segments comprises the substeps of:

dividing each subframe into nonoverlapping subdomain segments; and

decimating the subframe by a factor of two and performing corresponding fractal transformations.

6. A method as recited in claim 5 wherein the substep of dividing each subframe into nonoverlapping subdomain segments comprises creating subdomain segments of equal size.

7. A method as recited in claim 5 comprising selecting the decimated subframe that most closely matches the subdomain segments as the one that produces the minimum total root mean square difference.

9. A method for decoding a speech signal encoded by the method of claim 4 comprising the steps performed by a data processor of:

receiving an encoded speech signal;

separating the encoded speech signal into a prediction filter coefficients portion and an encoded error signal portion;

generating a predictive filters from the prediction filter coefficients portion;

storing a predetermined digital signal in a memory buffer designated as a source buffer;

determining from the encoded error signal the fractal transformation performed on an identified portion of the source buffer and applying that procedure to that portion of the source buffer;

storing the modified source buffer data in a separate buffer designated as the target buffer;

repeating the determining and target buffer storing steps, with the target buffer being considered as the source buffer, until predetermined criteria are met; and

providing the source buffer as input to the generated predictive filters to synthesize the digital speech signal.

8. A method for decoding a digital signal, comprising the steps performed by a data processor of:

receiving an encoded digital signal;

separating the encoded digital signal into a prediction filter coefficients portion and an encoded error signal portion;

generating an error signal from the encoded error signal portion using a fractal transformation procedure;

generating a predictive filter from the prediction filter coefficients portion; and

exciting the generated predictive filter with the generated error signal to produce the original digital signal.

10. A method for digital signal encoding and decoding comprising:

receiving a digital signal;

encoding the received digital signal using LPC methods to separate and encode a linear portion of the received digital signal to obtain a set of prediction filter coefficients;

encoding a residual portion of the received digital signal using a fractal transformation procedure to obtain an encoded error signal;

supplying the prediction filter coefficients and the encoded error signal as an encoded digital signal;

receiving an encoded digital signal;

separating the encoded digital signal into a prediction filter coefficients portion and a encoded error signal portion;

generating an error signal from the encoded error signal portion using a fractal transformation procedure;

generating a predictive filter from the prediction filter coefficients portion;

exciting the generated predictive filter with the generated error signal to produce the original digital signal.

11. A method as recited in claim 10 wherein the residual portion comprises a LPC residual signal.

12. A method for digital speech signal encoding and decoding comprising the steps performed by a data processor of:

receiving a digital speech signal;

generating a plurality of frames from the received digital speech signal;

performing a linear predictive code analysis on the frames to determine corresponding prediction filter coefficients;

comparing a speech signal based on the prediction filter coefficients with the received digital speech signal to create an error signal;

dividing the error signal into nonoverlapping subframes;

creating a plurality of range segments for the nonoverlapping subframes, where each range segment is represented by a fractal transformation procedure;

selecting, for the nonoverlapping subframes, the range segment which most closely corresponds to the nonoverlapping subframe;

representing the digital input as an encoded speech signal comprising the prediction filter coefficients and an encoded error signal corresponding to the fractal transformation procedure;

receiving the encoded speech signal;

separating the encoded speech signal into a prediction filter coefficients portion and an encoded error signal portion;

generating a predictive filter from the prediction filter coefficients portion;

storing a predetermined digital signal in a memory buffer designated as a source buffer;

determining from the encoded error signal the fractal transformation procedure performed on an identified portion of the source buffer and applying that procedure to that portion of the source buffer;

storing the modified source buffer data in a separate buffer designated as the target buffer;

repeating the determining and target buffer storing steps, with the target buffer being considered as the source buffer, until predetermined criteria are met; and

providing the source buffer as input to the generated predictive filters to synthesize the digital speech signal.

13. A method as recited in claim 12 wherein the step of creating a plurality of range segments comprises using the nonoverlapping subframes to create a plurality of range segments.

14. A method as recited in claim 13 wherein the step of creating a plurality of range segments comprises the substeps of:

dividing each subframe into nonoverlapping subdomain segments; and

reducing the size of the subframe by a factor of two and performing corresponding fractal transformation procedures.

15. A method a recited in claim 14 wherein the step of dividing each subframe into nonoverlapping subdomain segments comprises creating subdomain segments of equal size.

16. A method as recited in claim 15 wherein the step of using decoded error signals to generate a plurality of range segments comprises substeps of:

receiving an encoded speech signal;

separating the encoded speech signal into a prediction filter coefficients portion and an encoded error signal portion;

storing a predetermined digital signal in a memory buffer designated as a source buffer;

determining from the encoded error signal a fractal transformation procedure performed on an identified portion of the source buffer and applying that fractal transformation procedure to that portion of the source buffer;

storing the modified source buffer data in a separate buffer designated as the target buffer;

repeating the determining and target buffer storing steps, with the target buffer being considered as the source buffer, until predetermined criteria are met;

perform fractal transformation procedures on the source buffer; and

provide the source buffer as a range segment.

17. A method as recited in claim 16 wherein the step of storing a predetermined digital signal in a memory buffer comprises using a decoded error signal as the predetermined digital signal.

18. A method as recited in claim 15 comprising the steps of:

dividing each subframe into nonoverlapping subdomain segments;

decimating the subframe by a factor of two and performing corresponding procedures;

receiving an encoded speech signal;

separating the encoded speech signal into a prediction filter coefficients portion and an encoded error signal portion;

storing a predetermined digital signal in a memory buffer designated as a source buffer;

determining from the encoded error signal the fractal transformation procedure performed on an identified portion of the source buffer and applying that procedure to that portion of the source buffer;

storing the modified source buffer data in a separate buffer designated as the target buffer;

repeating the determining and target buffer storing steps, with the target buffer being considered as the source buffer, until predetermined criteria are met;

perform a fractal transformation on the source buffer; and

provide the source buffer as a range segment.

19. A method as recited in claim 18 wherein the step of dividing each subframe into nonoverlapping subdomain segments comprises creating subdomain segments equal in size.

20. A method as recited in claim 18 comprising selecting the range segment that most closely matches the domain segment as the range segment that produces the minimum total root mean square error difference.

21. A method as recited in claim 12 comprising using decoded error signals to generate a plurality of range segments.

22. A method as recited in claim 12 wherein the step of creating a plurality of range segments comprises using nonoverlapping subframes and decoded error signals to create a plurality of range segments.

23. An apparatus for encoding a digital signal comprising:

means for receiving the digital signal;

means for encoding the received digital signal using LPC methods to separate and encode a linear portion of the received digital signal;

to obtain a set of prediction filter coefficients;

means for encoding a residual portion of the received digital signal using a fractal transformation procedure to obtain an encoded error signal; and

means for supplying the prediction filter coefficients and the encoded error signal as an encoded digital signal.

24. An apparatus for decoding a digital signal comprising:

means for receiving an encoded digital signal;

separating the encoded digital signal into a prediction filter coefficients portion and an encoded error signal portion;

means for generating an error signal form the encoded error signal portion using a fractal transformation procedure;

means for generating a predictive filter from the prediction filter coefficients portion; and

means for exciting the generated predictive filter with the generated error signal to produce the original digital signal.

25. An apparatus for encoding and decoding a digital signal comprising:

means for receiving the digital signal;

means for encoding the received digital signal using LPC methods to separate and encode a linear portion of the received digital signal;

to obtain a set of prediction filter coefficients;

means for encoding a residual portion using a fractal transformation procedure to obtain an encoded error signal;

means for supplying the prediction filter coefficients and the encoded error signal as an encoded digital signal;

means for receiving the encoded digital signal;

separating the encoded digital signal into a prediction filter coefficients portion and an encoded error signal portion;

means for generating an error signal form the encoded error signal portion using the fractal transformation procedure;

means for generating a predictive filter from the prediction filter coefficients portion; and

means for exciting the generated predictive filter with the generated error signal to produce the original digital signal.

26. An apparatus for encoding a digital speech signal comprising:

means for receiving the digital speech signal;

means for creating a plurality of frames from the received digital speech signal;

means for performing a linear predictive code analysis and for determining the prediction filter coefficients for a frame;

means for producing an error signal by comparing the synthesized output of the linear predictive analysis with the received digital speech signal;

means for dividing the error signal into nonoverlapping subframes;

means for creating a plurality of range segments, where each range segment is represented by a fractal transformation procedure;

means for selecting, for each of the subframes, the range segment which most closely corresponds to the subframe according to predetermined criteria; and

means for representing the digital input as the prediction filter coefficients and the corresponding fractal transformation procedure used to develop the range segment that most closely corresponds to the subframe.

27. An apparatus for decoding a digital speech signal comprising:

means for receiving the encoded digital speech signal;

means for separating the encoded digital speech signal into a prediction filter coefficients portion and an encoded error signal portion;

means for generating predictive filters from the prediction filter coefficients portion;

means for storing a predetermined digital signal in a memory buffer, designated source buffer;

means for determining from the encoded signal a fractal transformation procedure performed on an identified portion of the source buffer and applying that procedure to that portion of the source buffer;

means for storing the modified source buffer in a separate memory buffer, designated target buffer;

means for swapping the content of the source and target buffer;

means for determining whether the source buffer should be modified again; and

means of providing the source buffer as output.

28. An apparatus for encoding and decoding a digital speech signal comprising:

means for receiving the digital speech signal;

means for creating a plurality of frames from the received digital speech signal;

means for performing a linear predictive code analysis and for determining the prediction filter coefficients for a frame;

means for producing an error signal by comparing the synthesized output of the linear predictive analysis with the received digital speech signal;

means for dividing the error signal into nonoverlapping subframes;

means for creating a plurality of range segments, where each range segment is represented by a fractal transformation procedure;

means for selecting, for each of the subframes, the range segment which most closely corresponds to the subframe according to predetermined criteria;

means for representing the digital input as the prediction filter coefficients and the corresponding fractal transformation procedure used to develop the range segment that most closely corresponds to the subframe;

means for receiving the encoded digital speech signal;

means for separating the encoded digital speech signal into a prediction filter coefficients portion and an encoded error signal portion;

means for generating predictive filters from the prediction filter coefficients portion;

means for storing a predetermined digital signal in a memory buffer, designated source buffer;

means for determining from the encoded signal the fractal transformation procedure performed on an identified portion of the source buffer and applying that procedure to that portion of the source buffer;

means for storing the modified source buffer in a separate memory buffer, designated target buffer;

means for swapping the content of the source and target buffer;

means for determining whether the source buffer should be modified again; and

means of providing the source buffer as output.