US 5,850,260 AGrant
Methods and Apparatus for Determining a Coding Rate to Transmit a Set of Symbols
Issue Date:1998-12-15
•31 Claims
•9 Drawing Sheets
Abstract
Apparatus and methods are provided for generating an output signal representing an initial Huffman Coding rate for use in compressing a received digital signal. The digital signal includes a plurality of digital sets wherein ones of the digital sets are non-unique. Ones of the digital sets are stored and an indicator is associated with each. The indicator represents the probability of occurrence, or frequency, of the associated digital set within the digital signal. While more than one associated indicator remains stored, pairs of the associated indicators are selectively combined and each of the selectively combined pairs of associated indicators are accumulated to determine the initial Huffman Coding rate. The initial Huffman Coding rate is used to compress the digital signal.
Metadata
Assignee
- Lucent Technologies Inc.
Inventor
- Jonathan David Rosenberg
Application Information
Application Number:US 3990842
Filing Date:1995-03-08
Priority Date:1995-03-08
Art Unit:273
Classifications
IPC:
H04N 514H04N 1102H04N 1104
Field of Search:
348358341375390-41642760-68;106;55253;240
Patent Drawings (9 sheets)
Description
Cross-Reference to Related Applications
The present invention is related to U.S. patent application Ser. No. 08/400,706, Attorney Docket No. Rosenberg 3, entitled "Apparatus and Methods for Selectively Reducing a Huffman Coding Rate"; U.S. Pat. No. 5,696,563, Attorney Docket No. Rosenberg 4, entitled "Apparatus and Methods for Performing Huffman Coding"; and U.S. Pat. No. 5,612,747, Attorney Docket No. Hartung 10-1, entitled "Method and Apparatus for Vector Quantization Caching in a Real Time Video Coder", which are all commonly assigned to the assignee of the present invention, and which are filed concurrently herewith. The disclosures of these related Applications are incorporated herein by reference.
Technical Field of the Invention
The present invention relates generally to signal compression, and in particular to apparatus and methods for determining an initial Huffman Coding rate.
Background
Conventional communication systems, including networks, include two or more interconnected nodes wherein each node functions as a junction point within the system. Information is transferred between nodes using electric, light, and/or radio waves, and typically involves transferring one or more codewords. Each codeword represents a symbol in a symbol set, such as an alphabet, and includes data for use by, and/or instructions for, a receiving node. Each codeword is defined by one or more binary digits, or bits.
Communication systems have limited bandwidth. In other words, there exists an upper limit, or maximum number, of bits which may be transferred per unit time. Contrary to this limitation is the need of many communication systems to transfer large quantities of symbols. This is particularly true in video applications, such as videophone and direct television, where video symbols typically represent chrominance and/or luminance values for picture elements ("pixels"), motion information, instructions indicating the content of the chrominance, and luminance values or marker codes. Marker codes are sync codes.
Data compression techniques have been incorporated into many communication systems to increase the number of codewords transferred given the available bandwidth. These techniques eliminate unnecessary data, redundancies, and the like from transmissions. Huffman Coding is one popular approach which is commonly used for video, audio/speech and high-speed data compression. Huffman Codes use variable length symbols wherein each symbol's length depends upon the probability of occurrence of the one or more codewords defining it.
Assume for example a symbol set of {bear, dart, wear, beet}. Each of the codewords used to represent the symbol set has a length inversely proportional to its symbol's usage. Assuming this symbol set is used in the English language, "wear" is likely to be said more often than "bear", more often than "dart", and more often than "beet". The coding may accordingly be {be, dar, w, beet}, where codeword length is equivalent to the number of letters. In point of fact, the English language presents another good example of variable length codewords wherein common words such as {it, in, a, car, the, if, I, a, an} are shorter than words used less frequently, such as {approximately, university, automobile, individually, myself, particularly}.
Source entropy is an optimal "loss-less" coding rate, in other words, the smallest average number of bits per symbol required to represent a particular symbol set or alphabet. Huffman Coding techniques have been found to reduce coding rates to nearly source entropy. In many conventional applications, such as video processing, however, the probability of all occurrences of the various symbols tends to change as the video image changes. This causes the current Huffman Codes to be an inefficient representation of the symbols. Worse, these changes typically occur at random.
The Huffman Codes accordingly cease to reduce coding rates to source entropy and require recalculation. This is often computationally difficult as the codeword for any one symbol depends on the probability of occurrence of the symbols in the alphabet. For large alphabets therefore each codeword, of which there are typically many, requires substantial computation.
One conventional solution periodically recalculates the Huffman Codes. Another solution determines the source entropy, and then estimates from that determination the coding rate for recalculating the Huffman Codes. Each approach is typically inaccurate, and in many situations demands substantially the same processing resource requirements needed to recalculate the Huffman Codes as when originally defined. The inability of conventional communication systems to generate, and regenerate, Huffman Codes to maintain substantially source entropy remains a dominant obstacle to producing high quality video, audio/speech and high-speed communication.
Summary of the Invention
An initial coding rate is calculated to determine the exact number of bits required to compress a plurality of digital sets or items, such as the symbols representing a plurality of motion vectors in a video processing application for example. This initial coding rate is derived in accordance with the present invention without generating the compressed code itself. Processing resource requirements are accordingly reduced.
Broadly, the present invention is directed to apparatus and methods for use in signal processing and/or communication, including without limitation, processing system networks (including local and wide area networks), telephony systems (including videophone and cellular technologies), direct television systems, satellite systems, land-mobile radio systems, broadcast systems, data storage/retrieval systems, and the like.
An apparatus in accordance with the principles of the present invention generates an output signal representing an initial coding rate for use in compressing digital signals, and includes receiving, storage and processing means. The receiving means operates to receive a digital signal. The digital signal includes a plurality of digital sets wherein particular ones of the digital sets are non-unique. The storage means operates to store the digital sets. The processing means operates to process the digital signal to generate the output signal. An important aspect of any apparatus in accordance with the present invention is that it may be processing system, firmware or hardware based.
The processing means is preferably operable to store ones of the digital sets in the storage means, and to associate with each of the stored digital sets an indicator representing the probability of occurrence, or frequency, of the associated digital set in the received digital signal. The processing means selectively combines pairs of the associated indicators, and accumulates each of the selectively combined pairs of associated indicators to determine the initial coding rate. This is preferably accomplished while more than one associated indicator remains stored.
One method in accordance with the principles of the present invention concerns processing a received digital signal to generate an output signal. The output signal represents an initial coding rate for use in compressing the received digital signal. The received digital signal includes a plurality of digital sets wherein ones of the digital sets are non-unique. The method preferably includes the steps of storing, associating, initializing, determining, ordering and generating the output signal.
More particularly, ones of the digital sets are stored. An indicator is associated with each one of the stored digital sets, and represents the probability of occurrence, or frequency, of the associated digital set in the digital signal. An accumulator representing the initial coding rate is initialized.
A determination is made of whether more than one associated indicator remains stored. The associated indicators, upon a determination that more than one is stored, are ordered. Two of the stored associated indicators are selectively combined, and the resulting selectively combined associated indicator is added to the accumulator. The determination step is preferably repeated until a single indicator remains, at which time the accumulator represents the initial coding rate.
A second method in accordance with the principles of the present invention concerns controlling a memory storage device to generate an output signal representing an initial coding rate. The coding rate is used in compressing a received digital signal which includes a plurality of digital sets. Particular ones of the digital sets are preferably non-unique.
Ones of the digital sets are stored in the memory storage device. Each stored digital set has associated therewith an indicator representing the probability of occurrence, or frequency, of the associated digital set within the digital signal. While more than one associated indicator remains stored, pairs of the associated indicators are selectively combined. In connection with each combination, each selectively combined pair of associated indicators is accumulated to determine the initial coding rate.
One embodiment for using and/or distributing the present invention is as software. The software embodiment includes a plurality of processing system instructions which are stored to a storage medium. Preferred storage mediums include without limitation magnetic, optical, or semiconductor chip, as well as suitably arranged combinations thereof. The processing system instructions are readable by a processing system, and upon execution, operate to control at least one processing system for compressing a signal using encoding techniques in accordance with the principles of the present invention.
Brief Description of the Drawings
For a more complete understanding of the present invention, and the advantages thereof, reference is now made to the following Detailed Description of the Invention, taken in conjunction with the accompanying drawings in which like numbers designate like parts, and in which:
FIG. 1 illustrates a block diagram of one exemplary system for compressing video data in accordance with the principles of the present invention;
FIG. 2 illustrates an isometric view of one exemplary processing system for compressing video data in accordance with the principles of the present invention;
FIG. 3 illustrates a block diagram of an exemplary microprocessing system which may be utilized in conjunction with the processing system of FIG. 2;
FIG. 4a illustrates a block diagram of an exemplary video processing system in accordance with the principles of the present invention;
FIG. 4b illustrates a block diagram of an exemplary processing system-based wireless local area network including videophone technologies in accordance with the principles of the present invention;
FIG. 4c illustrates a block diagram of an exemplary wireless communication system in accordance with the principles of the present invention;
FIG. 5a illustrates a conceptual diagram for coding an equiprobable L-ary source;
FIG. 5b illustrates a conceptual diagram for coding a nonequiprobable L-ary source;
FIG. 5c illustrates a conceptual diagram for Huffman Coding a nonequi-probable L-ary source;
FIG. 5d illustrates the generation of pointers for the conceptual diagram of FIG. 5c; and
FIG. 6 illustrates an exemplary flow diagram for processing a received input signal utilizing Huffman Coding techniques in accordance with the principles of the present invention; and
FIG. 7 illustrates an exemplary flow diagram for calculating an initial Huffman Coding rate in accordance with the principles of the present invention.
Detailed Description of the Invention
FIG. 1 illustrates a block diagram of one exemplary system for compressing video signals in which the principles of the present invention are particularly advantageous. The exemplary system includes a conventional video camera 101 and a video processing board 102. Video processing board 102 includes an analog-to-digital ("A/D") converter 103, a video compression processor 104 and two conventional memory storage devices, namely, a dynamic random-access memory ("DRAM") 105 and a static random-access memory ("SRAM") 106.
Video camera 101 may suitably be connected to A/D converter 103 to convert analog video signals produced by video camera 101 to a representative digital signal. A/D converter 103 may suitably be connected to video compression processor 104. Video compression processor 104 preferably has associated with it DRAM 105 as well as SRAM 106. Compressed video signals produced by video compression processor 104 may be transmitted over a data line 107.
In a preferred embodiment, camera 101 is a model no. YH-7B60, made by Sharp Corp., Osaka, Japan; A/D converter 103 is a model no. SAA7151, made by Philips' Gloeilampenfabrieken N.V., the Netherlands; and Video compression processor 104 is a model no. VCP rev 3, made by Integrated Information Technologies Inc., Santa Clara, Calif., USA. DRAM 105 and SRAM 106 are conventional suitably arranged storage devices. One preferred use of this video compression system is discussed in U.S. patent application Ser. No. 08/400,704, Attorney Docket No. Hartung 10-1, which is commonly assigned to the assignee of the present invention and which is incorporated herein by reference.
FIG. 2 illustrates an isometric view of an exemplary processing system 200 for compressing a video signal in accordance with the principles of the present invention. Processing system 200 is shown as a personal computer, and in one preferred embodiment is a model no. System 3333, by AT&T GIS, located in Dayton, Ohio. Processing system 200 may suitably be coupled with camera 101, and includes a hardware casing 201, having both a floppy disk drive 202 and a hard disk drive 203, a monitor 204 and a keyboard 205. Monitor 204 and keyboard 205 may be replaced by, or combined with, other conventional output and input devices, respectively.
Floppy disk drive 202 is operable to receive, read and write to external disks. Hard disk drive 203 is operable to provide fast access storage and retrieval. Floppy disk drive 202 may be replaced by or combined with any conventional suitably arranged structure for receiving and transmitting data and instructions, including without limitation, tape and compact disc drives, telephony systems and devices (including videophone technologies), and serial and parallel ports. In alternate embodiments, circuit boards, such as video processing board 102 of FIG. 1 for example, may be included.
Camera 101 is preferably coupled with processing system 200 through one of the aforementioned ports. In alternate embodiments, input video images may be received via one or more separate storage devices, such as a floppy disk or a compact disc, for example. An important aspect of the exemplary embodiment therefore is that data and/or instruction collection and compression need not occur coincidentally.
Note that hardware casing 201 is illustrated with a cut-away portion which includes a processing unit 206 suitably coupled with a memory storage device 207. Memory storage device 207 may be a random access memory ("RAM") or a read only memory ("ROM"), or other conventional suitably arranged memory storage device, such as DRAM 105 and/or SRAM 106 of FIG. 1 for example. Although processing system 200 is illustrated as having a single processing unit, a single hard disk drive and a single memory unit, processing system 200 may be equipped with a plurality of processing units and/or suitably arranged memory storage devices operable to cooperatively carry out the principles of the present invention.
It should be noted that although the present invention is particularly advantageous for use in video compression, the present invention is also well suited for use with other systems utilizing signal compression, including without limitation, processing system networks (including local and wide area networks), telephony systems (including videophone technologies), direct television systems, satellite systems, land-mobile radio systems, broadcast systems, information storage/retrieval systems, and the like.
Although a personal computer is utilized to illustrate one exemplary processing system embodiment, the principles of the present invention may be implemented within any processing system having conventional suitably arranged processing means for performing Huffman Coding in accordance with the principles of the present invention, including without limitation, cameras, video-phones, telephones, televisions, sophisticated calculators and, hand-held, laptop/notebook, mini, mainframe and super computers, including RISC and parallel processing architectures, as well as within processing system network combinations of the foregoing. Conventional processing system architecture is more fully discussed in Computer Organization and Architecture, by William Stallings, MacMillan Publishing Co. (3rd ed. 1993), which is incorporated herein by reference.
Other preferred embodiments of the present invention include, without limitation, implementations in firmware or hardware. Such exemplary embodiments may include suitably arranged circuitry, including programmable logic devices, such as PALs (programmable array logic), PLAs (programmable logic arrays) and DSPs (digital signal processors). Other exemplary embodiments may also include FPGAs (field programmable gate arrays) and ASICs (application specific integrated circuits), for example.
FIG. 3 illustrates a block diagram of one exemplary microprocessing system which may be utilized in conjunction with processing system 200. The microprocessing system may be programmed to compress signals using Huffman Coding techniques in accordance with the principles of the present invention. The microprocessing system includes a single processing unit 206 coupled via data bus 303 with a single memory storage device 207. Memory storage device 207 is operable to store one or more processing system instructions which processing unit 206 is operable to retrieve and execute. Processing unit 206 includes a control unit 300, an arithmetic logic unit ("ALU") 301, and a local memory storage device 302, such as, stackable cache or a plurality of registers, for example. Control unit 300 is operable to fetch processing system instructions from memory storage device 207. ALU 301 is operable to perform a plurality of operations, including addition and Boolean AND needed to carry out those instructions. Local memory storage device 302 is operable to provide local high speed storage used for storing temporary results and control information.
FIG. 4a illustrates a block diagram of an exemplary video/audio processing system in which the present invention is particularly advantageous. The exemplary system includes a single processing system 200, illustrated as a mainframe computer, coupled suitably with a plurality of conventional video cameras 401a-401n. Video cameras 401a-401n are positioned about a tennis stadium 402. Tennis stadium 402 includes two grand stands 403a, 403b and a tennis court 404. Each of the grand stands 403a, 403b includes a plurality of seats, some of which will be occupied by spectators 405 during a tennis match, as illustrated. Tennis court 404 is shown to include two tennis players 406a, 406b who oppose one another in the tennis match.
One or more of the video cameras 401a-401n operate to capture the tennis match from which representative video and/or audio signals are produced. The produced signals are input to processing system 200 wherein they are processed and compressed using Huffman Coding techniques in accordance with the principles of the present invention to produce one or more output signals. The produced output signals are transmitted to a plurality of televisions 407a-407m.
The televisions 407a-407m are located within a plurality of homes 408a-408m.
FIG. 4b illustrates a block diagram of an exemplary processing system-based wireless local area network ("LAN") in which the present invention is particularly advantageous. The illustrated LAN includes two exemplary processing system nodes 200a, 200b, shown as personal computers. Each of the processing system nodes 200a, 200b is coupled suitably with a conventional antenna 409a, 409b, respectively, and includes videophone technologies (not shown). Antennas 409a, 409b operate to transmit and receive wireless communications between processing system nodes 200a, 200b. The received wireless communications are processed utilizing representative electric signals. The illustrated LAN facilitates communications between users A and B, 410a, 410b, respectively, wherein each processing system node is operable to send, receive, process and compress video, audio and high speed signals in accordance with the principles of the present invention.
FIG. 4c illustrates a block diagram of an exemplary wireless communication system in which the present invention is particularly advantageous. The illustrated system includes a processing system 200, illustrated as a mainframe computer, which facilitates communication between a first node 411 and a second node 412. The first node 411 includes a first caller 413, shown utilizing a cellular telephone 414. The cellular telephone 414 is operable to send and receive wireless communication signals. The second node 412 includes a second user 415, shown utilizing a conventional telephone 416. The conventional telephone 416 is operable to send and receive wired communication signals. Processing system 200 is suitably coupled with the conventional telephone 416 and a conventional antenna 409. Antenna 409 operates to send and receive wireless signals to and from the cellular telephone 414. Processing system 200 is operable to send, receive, process and compress audio signals in accordance with the principles of the present invention.
The video, audio and/or high speed signals of FIGS. 4a-4c are compressed using Huffman Coding techniques in accordance with the principles of the present invention to produce one or more output signals. The output signals are real physical signals.
FIGS. 5a-5c illustrate the relationship between the entropy of a discrete source and the number of bits actually needed to encode that source. Block encoding is considered in each instance for which a symbol or sequence of symbols is mapped into a codeword, i.e., a block of bits. Recall that source entropy is a tight lower bound on minimum average codeword length.
FIG. 5a illustrates a conceptual diagram for coding an equiprobable L-ary source, wherein all symbols are equally probable and the number of symbols is a power of two, L=2.sup.k. The source entropy is k bits per symbol. Possible outputs are divided into two equal groups of 2.sup.k-1 symbols. The successive splits of the groups are designated "upper" and "lower" and if a zero and a one, respectively, are assigned, a minimum length code is generated.
FIG. 5b illustrates a conceptual diagram for coding a nonequiprobable L-ary source, wherein the powers are of 1/2. The probabilities may be P.sub.i =(1/2).sup.i+1, i=0,1, . . . , L-2; P.sub.L-1 =(1/2).sup.L-1, for example. Similar to FIG. 5a, the output is revealed in stages wherein the symbols are ordered with the highest probability symbol at the top, and the symbols are split into groups of equal probability. The first symbol is in one group and all of the other symbols are in the other. Note that the length of the codeword for the ith symbol is given by b.sub.i =-log.sub.2 P.sub.i.
In general, where output probabilities are arbitrary, it may be assumed that codewords are of lengths b.sub.i and satisfy
Averaging equation (1) over P.sub.i, it is found that
There accordingly exists an uniquely decipherable code whose word lengths conform to equation (1).
Huffman Codes provide codewords having a minimum average number of bits per symbol. Huffman Coding is a member of the class of codes called prefix codes wherein no codeword is the prefix of another codeword. For this codeword class, sequences of bits may be decoded uniquely and instantaneously.
FIG. 5c illustrates a conceptual diagram for Huffman Coding an nonequi-probable L-ary source. Huffman Coding techniques begin by listing the symbols in inverse order of probability. The two lowest probability symbols are combined, or added, into a group and a new list is formed with this group as a single entry. The list is resorted in inverse order of probability. The first step is repeated to form another list. At each step larger groups are formed and treated as a single entry. The process continues until the list contains only two entries. A zero is assigned to each member of one group and a one is assigned to each member of the other group. The process of grouping is then retraced; each of the groups is split and a zero and a one are assigned. FIG. 5d illustrates the generation of pointers for the conceptual diagram of FIG. 5c.
FIG. 6 illustrates an exemplary flow diagram for processing a received input signal utilizing Huffman Coding techniques in accordance with the principles of the present invention. For the purposes of the present discussion, the received input signal is assumed to be a video signal although the principles of the present invention may be advantageously used in conjunction with any signal compression apparatus, system or methodology. It is further assumed that the video signal is received at a constant frame rate, that each frame has a fixed number of bits, and that the bits are divided into three sections, namely, motion, vector quantization and scaler quantization information.
The process begins upon receipt of the input signal, processing block 601. If the input signal is an analog signal, it is preferably digitized, processing block 602. In the event that the signal is already in a digital format, this processing step is bypassed.
The video signal is preferably segmented into blocks wherein each block preferably contains k.times.k pixels, processing block 603. Although alternate embodiments may use non-square blocks. In the illustrative embodiment k is equal to eight, and each video frame preferably includes 8,960 pixels which are divided into 140 blocks (14 blocks horizontally and 10 blocks vertically). In alternate embodiments, particularly non-video embodiments, this processing step may be bypassed.
Motion estimation between consecutive video frames is preferably accomplished by comparing a current video frame with a previous reference video frame to determine one or more motion vectors corresponding to one or more blocks, processing block 604. This is preferably accomplished using forward motion estimation wherein each block of the current frame is searched for in the previous reference frame.
The techniques for calculating motion vectors are known, and may range from full search motion estimators to narrower selective search motion estimators, such as a coarse-fine search, for example. In video processing, selective search motion estimators are preferred due to reduced processing resource requirements. Assuming that a full search is done, it is preferable to use motion vectors in the range of -5 to 5 pixels at a resolution of 112.times.80, in increments of 1/3 pixels, for a total of 31 possible motion vectors in two dimensions. Sub-pixel motion estimation is accomplished by interpolating up to 336.times.240 resolutions, and then searching in a range of -15 to 15 pixels, in one pel increments.
The motion estimator is preferably biased towards a zero motion vector. If the prediction error for a particular motion vector is below a certain threshold, then zero motion is assumed in order to ensure that no motion is detected in regions of constant texture and to reduce source entropy coding rate as the zero-motion vector is coded with run-length codes. A motion vector is preferably obtained for each block.
Again, in alternate embodiments, particularly non-video embodiments, this processing step may be bypassed.
Recall that in order to compress signals for transmission (i.e., the motion vectors in the illustrated embodiment), a symbol set is typically utilized. More particularly, an array, or other suitable data structure or convention storage device, is preferably used as a catalogue representative of each unique symbol (presently, each unique motion vector) and its rate of occurrence, processing block 605.
An initial coding rate is calculated to determine the exact number of bits required to compress the symbols representing the motion vectors to be transmitted, processing block 606. This is preferably accomplished without generating the Huffman Code itself. The preferred method for calculating the initial coding rate will be discussed in detail with reference to FIG. 7. A variable representing the current coding rate is set equal to the initial coding rate, processing block 607.
Recall that communication systems have limited bandwidth, i.e., a maximum rate at which bits may be transferred per a given time period. Recall further that compression techniques, and in particular Huffman Coding techniques, are incorporated into conventional communication systems to increase information throughput, i.e., the number of codewords transferred given the available bandwidth. A determination of whether the current coding rate is greater than the maximum rate is made, decisional block 608. If the current Huffman Coding rate is greater, YES branch of decisional block 608, then the current coding rate must be modified. This is preferably accomplished by selectively reducing the current source entropy coding rate, processing block 609. The preferred processing steps for selectively reducing the current coding rate are more fully discussed in U.S. patent application Ser. No. 08/400,706, Attorney Docket No. Rosenberg 3, which is commonly assigned to the assignee of the present invention and which is incorporated herein by reference. The process repeats these steps until the current coding rate is less than or equal to the maximum rate, decisional block 608.
If the current coding rate is less than or equal to the maximum rate, NO branch of decisional block 608, then a Huffman Code is generated in accordance with the principles of the present invention, processing block 610. The preferred processing steps for generating the Huffman Code representing the current symbol table are more fully discussed in U.S. patent application Ser. No. 08/400,707, Attorney Docket No. Rosenberg 4, which is commonly assigned to the assignee of the present invention and which is incorporated herein by reference.
In the illustrated embodiment, the codewords are preferably retrieved from a code book, processing block 611. A representative bit stream is generated, which in the illustrated embodiment represents the reconstructed video frame, processing block 612.
FIG. 7 illustrates an exemplary flow diagram for calculating an initial Huffman Coding rate in accordance with the principles of the present invention. The initial coding rate is calculated to determine the exact number of bits required to compress the symbols representing the motion vectors to be transmitted. In accordance with the present invention, this is preferably accomplished without generating the compressed code itself. Processing resource requirements are accordingly reduced, which is an important aspect of the present invention.
The process begins upon receipt of a digital signal, input/output block 701. The digital signal preferably includes a plurality of digital sets wherein one or more of the digital sets are non-unique. The digital sets are representative of a plurality of symbols, which in the illustrated embodiment represent the motion vectors to be transmitted. Each of the digital sets is preferably stored once in association with an indicator representing the probability of occurrence, or frequency, of its digital set within the received digital signal, processing block 605.
A memory storage space, i.e., a variable, is preferably used as an accumulator to represent an initial coding rate. In alternate embodiments, conventional counting or adding devices may suitably be arranged to perform this function. The accumulator is preferably initialized, processing block 702.
A determination is preferably made as to whether more than one associated indicator has been stored, decisional block 703. Upon a determination that more than one associated indicator has been stored, YES branch of decisional block 703, the associated indicators are preferably ordered, or sorted, processing block 704. Two of the associated indicators are selectively combined such that the two indicators representing the least probability of occurrence are preferably combined, processing block 705. The selectively combined indicators are added to the accumulator, processing block 706. The process returns to decisional block 703.
Upon a determination that a single indicator remains, NO branch of decisional block 703, the accumulator is used to generate an output signal representing the initial coding rate, input/output processing block 707.
Assume, for example, that there are three symbols, A, B and C, with rates of occurrence of 15, 12 and 8, respectively. The accumulator is set to zero.
At a first stage, it is determined that more than one associated probability of occurrence indicator has been stored. The associated indicators of B and C are selectively combined ("BC") with a resulting rate of occurrence of 20. This implies that the compressed code for digital sets B and C will increase by length one. Since there are 12 occurrences of B and eight occurrences of C, 20 bits are required to transmit B and C thus far. 20 is accordingly added to the accumulator, bringing its total to 20.
At a second stage, it is determined that more than one associated probability of occurrence indicator has been stored. A and BC are selectively combined ("ABC") with an associated rate of occurrence of 35. This implies that the compressed code for digital sets A and BC will increase by length one. Since there are 15 occurrences of A and 20 occurrences of BC, 35 bits are required to transmit A and BC. 35 is therefore added to the accumulator, bringing the accumulator total to 55.
Since only a single indicator remains, ABC, the accumulator represents an initial coding rate.
Recall that a preferred embodiment for using and/or distributing the present invention is software. The software embodiment may be implemented in any suitable programming language. A "C" programming language implementation for performing the aforementioned processing steps is attached herewith as an appendix. The preferred implementation requires that only the rates be stored, and not the connections between the digital set, or symbols. At every stage, the two smallest occurrence rates are preferably combined and added to the accumulator. The combined rate takes the place of the two smallest occurrence rates. The procedure iterates until there is one rate remaining.
Although the present invention and its advantages have been described in detail, it should be understood that various changes, substitutions and alterations can be made herein without departing from the spirit and scope of the invention.
Claims
I claim:
1. A method for controlling a memory storage device to generate an output signal representing an initial coding rate for use in compressing a received digital signal, said digital signal including a plurality of digital sets representing symbols to be coded wherein ones of said digital sets are non-unique, said method comprising the steps of: storing ones of said plurality of the digital sets in said memory storage device; associating with each one of said stored digital sets an indicator representing the probability of occurrence of said associated digital set within said digital signal; combining selectively pairs of said plurality of said associated indicators, and accumulating each of said selectively combined pairs of said associated indicators to determine said initial coding rate; and generating output signal representing the initial coding rate for use in compressing the received digital signal without needing to code said received digital signal.
2. The method as set forth in claim 1 further including the step of compressing said received digital signal utilizing said output signal.
3. The method as set forth in claim 2 further including the step of Huffman Coding said received digital signal.
4. The method as set forth in claim 1 wherein said selectively combining step further includes the step of determining whether more than one indicator remains stored.
5. The method as set forth in claim 4 further including the step of generating said output signal in response to said determining step.
6. The method as set forth in claim 1 further including the steps of: receiving an analog signal; and converting said analog signal to said digital signal.
7. The method as set forth in claim 6 wherein said analog signal is a video signal, and further includes the step of storing said video signal on a video frame by video frame basis.
8. The method as set forth in claim 7 further including the step of segmenting said stored digital signal into a plurality of digital segments.
9. The method as set forth in claim 8 further including the step of determining at least one motion vector for ones of said plurality of digital segments.
10. The method as set forth in claim 9 wherein a first digital segment is present in a first video frame and a second video frame, and said determining step further includes the step of searching said first video frame for said first digital segment.
11. The method as set forth in claim 9 further including the step of comparing ones of said motion vectors with a threshold value.
12. The method as set forth in claim 11 further including the step of initializing, in response to said comparison step, particular ones of said motion vectors.
13. An apparatus for generating an output signal representing an initial coding rate for use in compressing digital signals, said apparatus comprising: receiving means for receiving a digital signal, said received digital signal including a plurality of digital sets representing symbols to be coded wherein ones of said digital sets are non-unique; storage means for storing said digital sets; and processing means for processing said received digital signal to generate said output signal, said processing means operable to: store ones of said digital sets in said storage means; associate with each one of said stored digital sets an indicator representing the probability of occurrence of said associated digital set within said received digital signal; combine selectively pairs of said associated indicators, and accumulate each of said pairs of said selectively combined associated indicators to determine said initial coding rate; and generate said output signal representing the initial coding rate for use in compressing the received digital signal without needing to code said received digital signal.
14. The apparatus as set forth in claim 13 wherein said processing means is further operable to compress said received digital signal utilizing said output signal.
15. The apparatus as set forth in claim 14 wherein said processing means is further operable to Huffman Code said received digital signal.
16. The apparatus as set forth in claim 13 wherein said processing means is further operable to determine whether more than one indicator remains stored.
17. The apparatus as set forth in claim 7 wherein said processing means is further operable to generate said output signal in response to said determination.
18. The apparatus as set forth in claim 13 wherein said processing means includes at least one processing unit.
19. The apparatus as set forth in claim 13 wherein said storage means is further operable to store a plurality of processing system instructions for directing said processing means to process said digital signal to generate said output signal.
20. The apparatus as set forth in claim 19 wherein said processing means is further operable to retrieve and execute selected ones of said plurality of processing system instructions.
21. The apparatus as set forth in claim 13 further including: an input port for receiving an analog signal; and an analog-to-digital converter operable to convert said analog signal to said digital signal.
22. The apparatus as set forth in claim 21 wherein said analog signal is a video signal, and said processing means is further operable to store said video signal on a video frame by video frame basis.
23. The apparatus as set forth in claim 22 wherein said processing means is further operable to segment said stored digital signal into a plurality of digital blocks.
24. The apparatus as set forth in claim 23 wherein said processing means is further operable to determine at least one motion vector for ones of said plurality of digital blocks.
25. The apparatus as set forth in claim 24 wherein a first block is present in a first video frame and a second video frame, and said processing means is further operable to search said first video frame for said first block.
26. The apparatus as set forth in claim 24 wherein said processing means is further operable to compare ones of said motion vectors with a threshold value.
27. The apparatus as set forth in claim 26 wherein said processing means is further operable to initialize, in response to said comparison, particular ones of said motion vectors.
28. A method for processing a received digital signal to generate an output signal representing an initial coding rate, said digital signal including a plurality of digital sets representing symbols to be coded wherein ones of said plurality of digital sets are non-unique, said output signal for use in compressing said digital signal, said method comprising the steps of: (a) storing ones of said plurality of digital sets; (b) associating an indicator with each one of said stored digital sets, each said indicator representing the probability of occurrence of said associated digital set in said digital signal; (c) initializing an accumulator representing said initial coding rate; (d) determining whether more than one associated indicator remains stored; (e) ordering, upon a determination that more than one associated indicator remains stored, said associated indicators, combining selectively two of said ordered associated indicators, adding said selectively combined associated indicators to said accumulator, and returning to step (d); and (f) generating said output signal representing the initial coding rate for use in compressing the received digital signal utilizing said accumulator without needing to code said received digital signal.
29. A method for controlling a memory storage device to generate an output signal representing an initial coding rate for use in compressing a received digital signal, said digital signal including a plurality of symbols to be coded, said method comprising the steps of: generating a plurality of digital sets representing the symbols to be coded, each said digital set comprising a codeword and an indicator, said digital set representing a probability of occurrence of the symbol corresponding to said digital set within said digital signal; associating with each one of said digital sets an indicator representing the probability of occurrence of said associated digital set within said digital signal; combining selectively pairs of said plurality of said associated indicators; accumulating each of said selectively combined pairs of said associated indicators to determine said initial coding rate; and generating said output signal representing said initial coding rate for use in compressing the received digital signal without needing to code said received digital signal.
30. An apparatus for generating an output signal representing an initial coding rate for use in compressing digital signals, said apparatus comprising: receiving means for receiving a digital signal, said received digital signal including a plurality of symbols to be coded; generating means for generating a plurality of digital sets representing the symbols to be coded; storage means for storing said digital sets; and processing means for processing said received digital signal to generate said output signal, said processing means operable to: store ones of said digital sets in said storage means; associate with each one of said stored digital sets an indicator representing the probability of occurrence of said associated digital set within said received digital signal; combine selectively pairs of said associated indicators; accumulate each of said pairs of said selectively combined associated indicators to determine said initial coding rate; and generate said output signal representing the initial coding rate for use in compressing the received digital signal without needing to code said received digital signal.
31. A method for processing a received digital signal to generate an output signal representing an initial coding rate, said digital signal including a plurality of symbols to be coded, said method comprising the steps of: a) generating a plurality of digital sets representing the symbols to be coded; b) associating an indicator with each one of said digital sets, each said indicator representing the probability of occurrence of said associated digital set in said digital signal; c) initializing an accumulator representing said initial coding rate; d) determining whether more than one indicator remains stored; e) ordering, upon a determination that more than one associated indicator remains stored, said associated indicators, combining selectively two of said ordered associated indicators, adding said selectively combined associated indicators to said accumulator, and returning to step (d) until only one indicator remains stored; and (f) generating said output signal representing the initial coding rate for use in compressing the received digital signal utilizing said accumulator without needing to code said received digital signal.
Patent Citations (15)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US3701111 | 1972-10-01 | Cocke et al. | |
| US4396906 | 1983-08-01 | Weaver | |
| US4541012 | 1985-09-01 | Tescher | |
| US4672441 | 1987-06-01 | Hoelzlwimmer et al. | |
| US4700175 | 1987-10-01 | Bledsoe | |
| US5079630 | 1992-01-01 | Golin et al. | |
| US5172228 | 1992-12-01 | Israelson | |
| US5389965 | 1995-02-01 | Kuzma | |
| US5420639 | 1995-05-01 | Perkins | |
| US5463699 | 1995-10-01 | Wilkinson | |
| US5541595 | 1996-07-01 | Meyer | |
| US5541640 | 1996-07-01 | Larson | |
| US5550541 | 1996-08-01 | Todd | |
| US5612747 | 1997-03-01 | Hartung et al. | |
| US5696563 | 1997-12-01 | Rosenberg |
Non-Patent Literature (1)
- Huffman, David A. "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the I.R.E., vol. 40, Sep. 1952, pp. 1098-1101.