Abstract:
An intelligence bearing signal in the form of a string of digitized analog signals is communicated from a source site to a destination site. The signal is in the form of a string of digitized analog signal samples. A sub-string dictionary, a linked list and an ID list are provided at the source site and the destination site, and are used to compress the intelligence bearing signal for faster transmission.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    Noiseless/lossless data compression greatly increases communication speed and memory capacity without degrading data integrity. One conventional method of lossless data compression used for text compression is called autosophy data communication. In this process, each text word is replaced by a preassigned word-number or address token that is associated with the word. Only the address tokens are communicated from a source site to a destination site. Each of the sites contains identical libraries of words and the corresponding word-number or address token. When a destination site receives a string of address tokens, the destination site uses the library to reconstruct the string of words originally input at the source site. This scheme is simple to implement, but is text-based and has limited compression capability.  
           [0002]    Many schemes exist to compress intelligence bearing signals, such as sound or voice. However, there is a significant need for faster schemes to compress intelligence bearing signals, particularly toll-grade speech, so that existing communication media, such as fiber optic telephone cables, can be used more efficiently. The present invention fulfills such a need.  
         BRIEF SUMMARY OF THE INVENTION  
         [0003]    An intelligence bearing signal is communicated from a source site to a destination site. The signal is in the form of a string of digitized analog signal samples. A sub-string dictionary, a linked list and an ID list are provided at the source site and the destination site. The sub-string dictionary has a plurality of entries. Each entry is a unique sub-string having a defined length. The linked list has a plurality of entries. The linked list entries include an address pointer to the start of each sub-string in the sub-string dictionary. The ID list has a plurality of entries. Each entry in the ID list contains the characteristics of each sub-string, and a pointer to the linked list entry that points to the first sub-string entry that has the characteristics of a respective sub-string. In the communication process, a string of digitized analog signal samples are parsed into a plurality of sub-strings. The sub-string dictionary and the ID list are then used to identify any sub-strings in the sub-string dictionary that correspond to any of the sub-strings obtained by the parsing operation. Only the address pointer in the linked list that correspond to any identified sub-strings are communicated from the source site to the destination site. 
       
    
    
     BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS  
       [0004]    The foregoing summary, as well as the following detailed description of preferred embodiments of the invention, will be better understood when read in conjunction with the appended drawings. For the purpose of illustrating the invention, there is shown in the drawings embodiments which are presently preferred. It should be understood, however, that the invention is not limited to the precise arrangements and instrumentalities shown.  
         [0005]    In the drawings:  
         [0006]    [0006]FIG. 1 shows an input analog sample which has been parsed into two sub-strings, in accordance with the present invention;  
         [0007]    FIGS.  2 A- 2 E are flowcharts of event handlers for implementing the present invention;  
         [0008]    [0008]FIG. 3 shows a sample SList array in accordance with the present invention;  
         [0009]    [0009]FIG. 4 shows a sample PList array in accordance with the present invention  
         [0010]    FIGS.  5 A- 5 B, taken together, show a sample IDList array in accordance with the present invention; and  
         [0011]    [0011]FIG. 6 shows an example of a network that uses the present invention to provide voice communications between source and destination sites. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0012]    1. Overview of Present Invention  
         [0013]    A string of digitized analog signal samples is broken into sets of variable length sub-strings based upon certain values in the sub-string or characteristics of the sub-string. The digitized analog signals can be or can carry any intelligence information. Examples of such signals include, but are not limited to:  
         [0014]    (1) audio, speech, video, broadcast, radio, television, movie  
         [0015]    (2) measuring or sensory signals, such as EEG, ECG, seismic  
         [0016]    (3) noise or silence  
         [0017]    The sub-strings are referred to herein as “S-strings.” The S-strings, along with a length count, are stored in a dictionary named “SList.” Next, a pointer word containing the address of where the S-string entry starts in SList is created and stored into a linked list named “PList.” Each time an entry is made in the PList, the link pointers of the PList are updated. Then, an entry is created and stored into a third list, named “IDList.” Each IDList entry is a packet that contains the values or variables that identify the characteristics of the S-string, and a pointer to the PList entry that points to the first S-string entry having those values and/or characteristics.  
         [0018]    The values and/or characteristics of the S-string that are stored in the IDList include: (1) count of positive peaks, (2) offset to each positive peak, and (3) amplitude of each positive peak.  
         [0019]    Before an S-string is added to the SList, a search is done to determine if that S-string is already in the S-List. The S-List does not contain duplicate S-strings.  
         [0020]    Copies of SList, PList and IDList can be continuously updated and maintained on multiple devices at different locations throughout the world.  
         [0021]    One use of the present invention is to construct a copy of a digitized signal from sets of S-strings. Rather than transmitting a digital signal, the only data needed to construct the copy is one or more PList pointers.  
         [0022]    Absent any constraints, it would require an impractical amount of storage to hold all of the possible combinations in an intelligence bearing analog signal. However, certain, if not most, analog signals that carry intelligence information are composed of a very limited number of similar shaped strings, thereby limiting the range of possible combinations. For example, speech is a type of analog signal that is composed from a limited count of similar samples.  
         [0023]    Telephone systems capture and store speech via an AID converter as 8-bit, 8000 samples per second. Although it is numerically possible to represent 2 64000  unique combinations with 8-bits×8000 samples, the nature of speech does not permit that many combinations to exist in the real world. Using the terminology of the present invention, the number of different speech signal S-signals that are actually produced by humans are only a fraction of the potential unique S-signals that could theoretically be generated. The number of unique S-signals is limited by the range of possible physical shapes of the human vocal tract and the limited pronunciation sounds of any given native language. The number of unique S-signals is further limited when only a finite set of users employ the present invention at the same time.  
         [0024]    Other types of analog signals also have significantly less unique combinations than the theoretical maximum. Video signals, voiceless music signals, and measuring or sensory signals, such as EEG, ECG signals, also provide only a limited number of S-signals because a large percentage of the data is redundant. In fact, every analog signal bearing intelligible information is limited by the nature of the intelligence information that is being represented.  
         [0025]    2. Detailed Description  
         [0026]    [0026]FIG. 1 shows an input analog sample which has been parsed into two S-strings. Units of amplitude and time are shown to illustrate how the sample is parsed, and how S-strings are defined. The first S-string has a length of t=21 units, and the second S-string has a length of t=13 units. Each S-string also has the following characteristics:  
                                           First   (a)   Count of positive peaks - 4       S-string:   (b)   Offsets to each peak&#39;s highest point - 2.0, 3.0, 8.0, 5.0           (c)   Amplitude of each peak&#39;s highest point - 2.5, 1.0, 4.0,               1.0       Second   (a)   Count of positive peaks - 5       S-string   (b)   Offsets to each peak&#39;s highest point - 0.5, 4.5, 4.0, 2.5           (c)   Amplitude of each peak&#39;s highest point - 0.2, 0.3, 1.0,               0.5, 0.2                  
 
         [0027]    One preferred embodiment of the present invention is implemented using three 1-dimensional arrays, three types of data packets, three event handlers, and a plurality of subroutine functions.  
         [0028]    The three 1-dimensional arrays are:  
         [0029]    (1) SList  
         [0030]    (2) PList  
         [0031]    (3) IDList  
         [0032]    The three types of data packets are:  
         [0033]    (1) ID packet  
         [0034]    (2) S-string packet  
         [0035]    (3) Pointer packet  
         [0036]    The three event handlers are:  
         [0037]    (1) Process Input Analog Signals  
         [0038]    (2) Process Input S-string Packet  
         [0039]    (3) Process Input Pointer Packet  
         [0040]    The processes that use the present invention call the Event Handlers. The calling process supplies a pointer to the location of the data to be processed by the called Event Handler and the length of the data. The Event Handler returns a pointer to the location of the data produced by the Event Handler. The first word of all variable length data produced by an Event Handler has a count of the length of the data.  
         [0041]    Each event handler uses one or more of the following subroutine functions:  
         [0042]    (1) Find Highest Positive Peaks in S-string  
         [0043]    (2) Compute High Peaks Offset to each Positive Peak  
         [0044]    (3) Add an S-string to SList Array  
         [0045]    (4) Add an IDList Packet to IDList Array  
         [0046]    (5) Update PList Backward/Forward Link Pointers  
         [0047]    (6) Compare an IDList Packet to Packets in IDList Array  
         [0048]    (7) Compare an S-string to S-strings in the SList  
         [0049]    (8) Fuzzy Compare an S-string to S-strings in the SList  
         [0050]    (9) Construct an IDList packet  
         [0051]    (10) Construct an S-string packet  
         [0052]    (11) Construct a Pointer Packet  
         [0053]    (12) Write Analog Samples  
         [0054]    (13) Write S-string Packet  
         [0055]    (14) Write Pointer Packet  
         [0056]    FIGS.  2 A- 2 E are flowcharts of event handlers for implementing the present invention. The individual steps of the flowcharts are self-explanatory, and thus are not described in detail herein. The return codes associated with the event handlers are defined as follows:  
         [0057]    FIGS.  2 A- 2 C: EVENT HANDLER CODES for “PROCESS INPUT ANALOG SIGNALS” 
         [0058]    0=insufficient count of symbols (no encoding has taken place), send string “as is.” 
         [0059]    1=all of the symbols in the string are identical.  
         [0060]    2=new string (not on SList), add to SList, send S-string and its PList pointer, and add its values and/or characteristics to the IDList.  
         [0061]    3=S-string is in SList, send PList pointer (pointer address is also returned)  
         [0062]    4=new string (not in SList), add to SList, send S-string and its PList pointer  
         [0063]    [0063]FIG. 2D: EVENT HANDLER CODE for “PROCESS INPUT S-STRING PACKET” 
         [0064]    0=event completed  
         [0065]    [0065]FIG. 2E: EVENT HANDLER CODE for “PROCESS INPUT POINTER PACKET” 
         [0066]    0=not a valid S-string pointer  
         [0067]    1=point is valid  
         [0068]    [0068]FIG. 3 shows a sample SList array.  
         [0069]    [0069]FIG. 4 shows a sample PList array.  
         [0070]    FIGS.  5 A- 5 B, taken together, show a sample IDList array.  
         [0071]    By sending only PList pointers over a communication medium, the present invention allows for toll-grade speech to be transmitted (or to appear to be transmitted) at speeds as fast as 4000 bits per second (4 kb/s).  
         [0072]    [0072]FIG. 6 shows an example of a network  10  that uses the present invention to provide voice communications between two telephone company central offices  12 ,  14  connected via a fiber optic cable communication medium  16 , such as a submarine cable (e.g., the TransPacific fiber optic telephone cable). Each central office  12 ,  14  serve as the source and destination sites of the voice signals. Each central office  12 ,  14  includes a switching system  18  and transmission equipment  20 . In one configuration of the present invention, the switching system  18  is a domestic routing box, such as PBX equipment, and the transmission equipment is an international call box comprising DS1 or DS2 cards. In a conventional configuration, the switching system  18  and the transmission equipment  20  would be connected directly together. In FIG. 6, a box  22  is added between the switching system  18  and the transmission equipment  20 . The box  22  contains the contents of the present invention, as described above.  
         [0073]    The present invention may be implemented with any combination of hardware and software. If implemented as a computer-implemented apparatus, the present invention is implemented using means for performing all of the steps and functions described above.  
         [0074]    The present invention can be included in an article of manufacture (e.g., one or more computer program products) having, for instance, computer useable media. The media has embodied therein, for instance, computer readable program code means for providing and facilitating the mechanisms of the present invention. The article of manufacture can be included as part of a computer system or sold separately.  
         [0075]    It will be appreciated by those skilled in the art that changes could be made to the embodiments described above without departing from the broad inventive concept thereof. It is understood, therefore, that this invention is not limited to the particular embodiments disclosed, but it is intended to cover modifications within the spirit and scope of the present invention as defined by the appended claims.