Concatenation compression method

[0002] The present invention pertains to digital signal compression techniques for voice and data communications and, in particular, to a multiple compression method that saves memory space and facilitates real-time audio communication.

[0003] Personal computer users have discovered the Internet (a global network of computers) to be an effective vehicle for data and audio communication with remote sites. Because the Internet provides worldwide communication at a cost much lower than standard telephone rates, there is an increasing demand for expanding the capabilities of personal computers to enable real-time voice communication via the Internet. However, there are several limitations to existing technology that inhibit this goal.

[0004] Existing telephone lines, which were originally developed for analog voice communication, provide a narrow bandwidth communication link, typically in the range of 200 Hz to 3400 Hz. Because the transmission time for one bit of data is inversely proportional to the frequency, the rate of data transmission is restricted by the bandwidth limitation of telephone lines.

[0005] Another obstacle to the transmission of audio data in particular is the large amounts of computer memory and processing time needed to digitize audio data for use in the digital environment of the personal computer. As is known in the art, in order to transmit digitized audio data for real-time use, a data rate in the range of 20-22 kilobytes per second is typically necessary. However, use of a modem is required for modulating and demodulating digital signals for transmission over telephone lines. Most currently available modems can reliably handle only 1.8 kilobytes (14.4 kilobits) to 3.6 kilobytes (28.8 kilobits) per second.

[0006] In an effort to increase the rate of data transmission, encoding has been used to allow more than one bit to be represented by a single pulse shape or signal level. This has expanded to the development of integrated services digital network (ISDN) technology, an all-digital communications network. In the ISDN network, all voice, data, and other information, including still and moving images, is digitized and transmitted at high speed over a single, public switched network. The most common transmission method is to translate the binary digits into pulses, which are then transmitted across the network at up to 64 kbits/second. These digital pulses are less susceptible to noise than are corresponding analog signals.

[0007] In order to accommodate the narrow bandwidth of existing telephone lines and the low data transmission rate of modems used by the majority of personal computers, digitized data must be compressed prior to transmission and decompressed after reception. The disadvantage of existing compression programs is their high computational overhead, i.e., the substantial processing required to execute several million instructions per second (MIPS) and the large amount of memory needed to store the data.

[0008] Audio compression algorithms that may be used in accordance with the teachings of the present invention will be known to those skilled in the art. One technique is the autocorrelation method, of which one variation is described by Jean Larouche in “AutoCorrelation Method for High-Quality Time/Pitch Scaling,” published in 1994 by Telecom Paris, Department Signal, Paris, France. Another technique is the absolute value difference algorithm, which adds the absolute values of the difference between successive signal segments and finds the lowest difference. Also well known is the EIA/TIA IS-54 standard, which discloses an algorithm description that one or ordinary skill in the art could implement as a compression algorithm for use with the present invention. A further method is the well-known GSM coding algorithm publicly available through the European Standards Committee. There is also the G723 and G728 algorithms. All of the aforementioned public documents, codes and algorithms are incorporated herein by reference.

[0009] While the compression ratios and data rates achieved by means of the compression techniques described above could be used for audio transmission via the Internet, the cost, complexity and low signal quality is unacceptable for real-time audio communication. Hence, there is a need for a data compression method that has low computational overhead, a high compression ratio, and utilizes existing personal computer hardware and compression algorithms to achieve high-quality compression and decompression of real-time audio signals.

[0010] The present invention provides a method for compressing data, and, in particular, digital signals for real-time communication over the Internet in a personal computer environment. In accordance with the method of the present invention, a digital signal is received from a signal source. The digital signal is compressed to a first compressed signal and then compressed again to a second compressed signal. Ideally, the step of compressing the received digital signal includes application of a time scale compression algorithm to the received digital signal, and the step of compressing the first compressed signal comprises application of an audio or speech compression algorithm to the first compressed signal.

[0011] In accordance with another aspect of the present invention, a digital signal compression and decompression process is provided for real time implementation on personal computers having a digital signal processor associated therewith. The process comprises the steps of receiving at the digital signal processor a digital signal from a signal source; compressing the digital signal by removing wave form redundancy to obtain a compressed digital signal; compressing the compressed digital signal by application of an audio compression method to the compressed digital signal to obtain a multiple-compressed digital signal for transmission over standard telephone lines; receiving at a digital signal processing means the multiple-compressed digital signal from the telephone lines, decompressing the multiple-compressed digital signal with an audio decompression method to obtain an estimation of the compressed digital signal; and decompressing the compressed digital signal by inserting wave form redundancies in the compressed digital signal to obtain a real-time estimation of the original digital signal generated from the signal source.

[0012] In accordance with another aspect of the present invention, the step of compressing the digital signal comprises application of time scale compression to the digital signal. In one embodiment, the time scale compression includes a correlation compression algorithm. In another embodiment, the time scale compression includes an absolute difference algorithm. Other known time scale compression methods may also be used with the present invention.

[0013] In accordance with yet a further aspect of the present invention, a method of modifying digitized signals for storage, transmission, and reception by personal computers having a digital signal processor associated therewith is provided. The method comprises modifying original digitized signals received in the digital signal processor from a signal source by concatenating multiple compression methods to achieve low bit rate compressed signals for real-time transmission over standard telephone lines.

[0014] In accordance with a further aspect of the present invention, the method further comprises modifying the multiple-compressed digitized signals received in the digital signal processor from a source, such as a digital memory medium or the telephone lines by concatenating multiple decompression methods to achieve an accurate real-time estimation of the original digitized signals.

[0015] In accordance with yet another aspect of the present invention, the step of compressing digitized signals by concatenating multiple compression methods comprises a first compression method concatenated with a second compression method, and further where the step of decompressing the compressed digitized signals by concatenating multiple decompression methods comprises a first decompression method concatenated with a second decompression method.

[0016] In accordance with another aspect of the present invention, the first compression method comprises time scale compression that removes selected segments of the digitized signals to eliminate signal redundancy, and further wherein the first decompression method comprises time scale decompression that inserts duplicate selected signal segments into the compressed digitized signals.

[0017] In accordance with yet another aspect of the present invention, the time scale compression includes a correlation signal compression algorithm. Alternatively, the time scale compression includes an absolute value difference algorithm.

[0018] In accordance with another aspect of the present invention, the second compression method comprises audio compression, such as a standard speech compression algorithm.

[0019] As will be readily appreciated from the foregoing, the present invention utilizes existing compression algorithms and technology in a unique multiple compression process. By concatenating compression methods, a greater degree of signal compression is obtained while maintaining a high quality in the reproduced speech or audio data. Low computational overhead is achieved by matching compression techniques with existing hardware.

[0020] The foregoing and other features and advantages of the present invention will more readily appreciated as the same become better understood from the detailed description when taken in conjunction with the following drawings, wherein:

[0021] FIG. 1 is a flow chart illustrating the method of the present invention;

[0022] FIG. 2 is a flow chart illustrating the method of the present invention in the context of digital audio signal transmission; and

[0023] FIG. 3 is a flow chart of one representative time scale compression method for use with the present invention.

[0024] The present invention is directed to the compression of electronic signals for subsequent processing, storage and/or transmission to a remote site and the corresponding decompression of the received signals. While representative embodiments will be described in the context of real-time speech transmission, it will be understood that the methods described herein can be adapted for use in the processing, storage and/or transmission of audio and non-audio data.

[0025] The concatenation method of the present invention may be practiced with existing communication software and hardware, as will be evident to one skilled in the art. The present invention is related to co-pending applications entitled System And Method For Dynamically Reconfigurable Packet Transmission; ISDN—Terminal Adaptor Using Digital Signal Processor. While the present invention is compatible with existing communication software and hardware, better results will be achieved utilizing the inventions disclosed in the related applications referenced above.

[0026] Analog audio signals and, in particular, voice and speech signals, must be digitized prior to processing by personal computers. Further processing signal compression is required to enable transmission of the digital signals over the narrow bandwidth of standard telephone lines as previously described. While available compression algorithms achieve sufficiently low data bit rates for their purposes, real-time processing of speech requires greater compression at faster speeds without loss of signal quality.

[0027] In one embodiment of the present invention, a digital audio signal is subjected to multiple compressions prior to processing and subsequent corresponding multiple decompressions. Thus, as shown in FIG. 1, the digital signal 10 is subjected to a first compression 12, resulting in a first compressed signal output. The output of the first compression 12 is then subjected to a second compression 14. This results in a multiple-compressed signal that may be further compressed, as desired, or it may be processed for storage or transmission.

[0028] This multiple algorithm speech compression may be applied to real-time voice or speech transmission as described below. The goal of signal compression is the elimination of signal wave form redundancy. After a compression algorithm is applied to a source data, the output may still contain redundancy. In the present invention, if the output of the first compression is suitable for the application of another compression algorithm, further compression can be achieved.

[0029] For example, let S(n) and O(m) be the input and output of a first compression algorithm respectively:

[0030] With the foregoing concatenation, signal redundancy can be substantially reduced. Concatenation of additional compression algorithms may be done to eliminate additional redundancy. To concatenate two algorithms in the context of encoder and decoder output, the following operations take place:

[0031] As shown in FIG. 2, an audio signal input 16 is received into an analog-to-digital converter for analog to digital conversion 18. Because personal computers operate in a digital environment, analog speech signals must be converted into digital format for subsequent processing and transmission. The audio signal source may be a microphone, telephone or other similar device that generates analog signals. These analog signals are then converted into digital format by the analog-to-digital converter. Following conversion, the digital audio signal is received at a digital signal processor (DSP) 20 for compression. As was briefly explained above, digitized audio signals consume large amounts of computer memory for storage and computer processing time. The storage and transmission of large amounts of information by personal computers via standard telephone lines, such as are used by the Internet, is not feasible due to signal distortion and loss of data caused by the narrow bandwidth of the communication lines. Consequently, compression of the digital audio signals is required.

[0032] As shown in FIG. 2, the digital audio signal is received by the DSP 20 where time scale modification or compression 22 is used to compress the signal. Time scale compression 22 of a signal consists of removing wave form redundancy from the original signal in such a way that the original information is maintained. Various algorithms have be en developed for time scale compression, as will be discussed more fully below. The application of time scale compression to the digital audio signal results in a first compressed audio signal. The compressed audio signal is then passed to the audio compression stage 24 where the first compressed audio signal is further compressed by application of an audio compression algorithm. Several audio or speech compression algorithms as described herein are readily available to those skilled in the art. Application of the speech compression algorithm to the compressed audio signal results in a multiple-compressed signal that is eventually modulated for transmission 26 over telephone lines using standard transmission methods.

[0033] The transmission 26 of the multiple-compressed signal is followed by reception of the signal in a second digital signal processor (DSP) 28. Decompression 30 of the multiple-compressed signal is first undertaken to yield an estimation of the compressed audio signal. This is then followed by a decompression 32 of the compressed audio signal to yield an estimation of the digital audio signal. The digital audio signal is then passed to a digital-to-analog converter for digital-to-analog conversion 34. The resulting audio signal output 36 is converted to discernible sound by conventional methods.

[0034] In accordance with another embodiment of the present invention, wave form redundancy elimination in the T1 compression described above can be used in combination with any existing speech compression algorithm in T2 to achieve an improved compression rate and improved quality in the speech output. Preferably, the elimination of wave form redundancy is accomplished through time scale modification. Thus, T1 is time compression and InvT1 is time stretching. T1 is the discarding of selected similar portions of the speech wave form and InvT1 is duplicating selected similar portions of the compressed speech wave form. Similarly, T2 is the application of a speech compression algorithm to further compress the time scale modified signal and the InvT2 is decompressing the multiple-compressed speech wave form.

[0035] In the T1 operation: Search the similar portion of the speech wave form every pitch duration (roughly 10 to 15 ms); and discard the similar portion of speech to get a compression in the range of 1.01:1 to 22:1, and ideally a 2:1 compression.

[0036] In the T2 operation: Using any existing speech compression algorithm (for example GSM, G728, G721, and other similar algorithms) to achieve a multiple-compressed signal. In the preferred embodiment, using a GSM as the T2 results in a bit rate of 13.5 kbits/2=6.75 kbits/sec.

[0037] In the InvT2 operation: Using a corresponding decompression algorithm to decompress the multiple-compressed signal and obtain an estimation of the first compressed signal.

[0038] And finally, in the InvT1 operation: Search the similar portion of the output of the InvT2 operation every pitch duration and duplicate this portion to accomplish time stretching of the compressed signal, thereby obtaining an estimation of the original input signal.

[0039] While it may seem counter-intuitive to combine multiple compression algorithms when the goal is a faster compression rate with high quality, the concatenation compression method of the present invention achieves unexpectedly good results. When combined with the compatible hardware and signal processing equipment described herein, a reliable, high quality signal transmission can be obtained in a real-time environment with low computational overhead.

[0040] Referring next to FIG. 3, illustrated therein is one example of a time scale modification algorithm for compressing speech signals. The absolute difference method illustrated in FIG. 3 uses signal sampling to locate and discard small pieces of the original signal or duplicating the same in the reverse decompression process.

[0041] In the absolute difference method, successive signal samples 40 are measured 42 to quantify the absolute value of the difference between successive samples, which are then summed. A determination of the lowest difference 44 is made by comparing the sums of the absolute values. The signal samples with the lowest difference are identified 46 and discarded. This results in a compression of the signal in the time domain without affecting the pitch.

[0042] It is to be understood that other time scale modification techniques may be used in the first compression without departing from the spirit and scope of the present invention. However, it has been found that the technique best suited for an application will depend on the hardware used. More particularly, while the absolute difference technique is easy to implement with a high level language such as C++, the C++ code requires too many processing cycles. The traditional correlation method is much simpler when a fixed point digital signal processor is used.

[0043] While a preferred embodiment of the invention has been illustrated and described, it is to be understood that various changes may be made therein without departing from the spirit and scope of the invention. For instance, while a preferred time scale modification ratio of 2:1 has been described, it is to be understood that almost any ratio can be used, depending on the level of quality desired. For instance a three to one compression ratio will result in some loss of information. Whether that loss is acceptable will depend on the parameters of the application. In addition, while a high level language such as C++ has been described in conjunction with the present invention because of its prevalent use in Internet telecommunication applications and in the application interface, it will be appreciated by those skilled in the art that any language can be used to implement the present invention. Thus, the scope of the present invention is to be limited only by the claims that follow.