[go: up one dir, main page]

WO1998021889A1 - Procedes et dispositif pour analyseur de train binaire programmable destine a des systemes audiovisuels et de decodage generique - Google Patents

Procedes et dispositif pour analyseur de train binaire programmable destine a des systemes audiovisuels et de decodage generique Download PDF

Info

Publication number
WO1998021889A1
WO1998021889A1 PCT/US1996/017876 US9617876W WO9821889A1 WO 1998021889 A1 WO1998021889 A1 WO 1998021889A1 US 9617876 W US9617876 W US 9617876W WO 9821889 A1 WO9821889 A1 WO 9821889A1
Authority
WO
WIPO (PCT)
Prior art keywords
program
data
bitstream
mode
mode selection
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/US1996/017876
Other languages
English (en)
Inventor
Alexandros Eleftheriades
Yihan Fang
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Columbia University in the City of New York
Original Assignee
Columbia University in the City of New York
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Columbia University in the City of New York filed Critical Columbia University in the City of New York
Priority to PCT/US1996/017876 priority Critical patent/WO1998021889A1/fr
Priority to US09/297,714 priority patent/US6512775B1/en
Publication of WO1998021889A1 publication Critical patent/WO1998021889A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F40/00—Handling natural language data
    • G06F40/20—Natural language analysis
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformation of program code
    • G06F8/41—Compilation
    • G06F8/42—Syntactic analysis
    • G06F8/427—Parsing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
    • H04N21/40—Client devices specifically adapted for the reception of or interaction with content, e.g. set-top-box [STB]; Operations thereof
    • H04N21/41—Structure of client; Structure of client peripherals
    • H04N21/426—Internal components of the client ; Characteristics thereof

Definitions

  • the present invention relates to techniques for parsing a digital bitstream, and more specifically, to programmable audiovisual and generic bitstream parsing techniques .
  • coded bitstreams which represent audiovisual or other generic data.
  • bitstreams In order to be usable by the receiving system, not only must such coded bitstreams must be decoded, but the bitstream must be parsed, i.e., separated into semantically meaningful units or "objects. "
  • bitstream in the case of an MPEG-2 encoded bitstream, the bitstream must be parsed into slices and macroblocks before the information contained in the bitstream is usable by an MPEG-2 decoder.
  • the MPEG-2 decoder uses the parsed bitstream to reconstruct the original audiovisual information.
  • the parsing operation has been performed by custom-manufactured hardware and/or software.
  • Such bitstream parsers would be programmed to separate an incoming bitstream based on some preselected objective rules or criterion, such as the intrinsic characteristics of packets of information in the bitstream, or transitions in characteristics between consecutive packets of information.
  • An example of such a parser is presented in United States Patent No. 5,414,650 issued May 9, 1995, to Hekhuis.
  • bitstream parser a significant problem with such a bitstream parser lies in the fact that the parsing rules are inflexible to changes in the syntax of the incoming bitstream. For this reason, there have been several attempts to construct bitstream parsers which are in some sense "programmable" so that bitstreams with differing syntax can be accepted by the same parser by reprogramming, rather than replacing, the parser.
  • United States Patent No. 5,371,547 issued Dec. 6, 1994, to Siracusa et al .
  • the apparatus includes a parser which separates transport header data and encoded MPEG payloads for presentation to an MPEG decoder in a suitable format.
  • the parser which examines each transport header to determine if the corresponding payload contains slice data, may be programmed to respond to the particular encoded protocol .
  • European Patent Application No. 94107818 published July 12, 1994, of Matsushita Electric Industrial Co., Ltd.
  • the apparatus includes a variable length decoder ("VLD") for parsing an input bitstream and for extracting quantization parameters and/or quantized coefficients from other information.
  • VLD variable length decoder
  • DSP programmable digital signal processor
  • the prior art techniques do not provide for self-configuration of the parser based on the syntax of the bitstream, but require external programming to adapt to changes in the bitstream syntax. Therefore, there exists a need in the art for a bitstream parsing technique which is fully adaptable to the syntax used in the bitstream without the requirement of interrupting the parsing operation to reprogram the bitstream parser every time a new syntax is encountered.
  • An object of the present invention is to provide a bitstream parsing technique which is programmable by the bitstream itself.
  • a further object of the present invention is to provide a parsing technique which is capable of redefining objects, recognizing certain context- sensitive objects, and recognizing certain repetitive objects during the parsing operation.
  • a still further object of the present invention is to provide an audiovisual and generic bitstream parsing technique which is programmable by an incoming bitstream that contains programming software embedded into the audiovisual or generic data, so that the parsing process may be tailored depending on the specific application.
  • the present invention provides a parser for parsing a digital bitstream which includes both data information and programming information.
  • the parser includes a buffer, a mode selector, a control circuit, and a data processor.
  • the mode selector determines whether one or more bits of the bitstream segment represent a mode selection code, and selects a parser mode in response to the mode selection code.
  • the control circuit receives and stores bits from the buffer when the bitstream parser is in a program mode in order to reprogram the control circuit with newly received program information, and uses the program information to generate one or more parsing signals when the bitstream parser is in a data mode .
  • the data processor receives bits from the buffer and parsing signals from the command circuit when the bitstream parser is in the data mode, and parses the received bits in accordance with the parsing signals.
  • the buffer is a shift buffer having a plurality of parallel outputs for bits of the bitstream segment which it stores
  • the parser includes one or more buffer isolation gates to isolate each parallel output of the shift buffer and to provide one or more non-isolated bits of the bitstream segment to the data processor and the control circuit.
  • the program mode selection and data mode selection codes are simply start and end program codes, respectively.
  • the mode selector advantageously includes a first logic circuit which receives one or more bits of the bitstream segment from the buffer isolation gates, compares such bits with one or more bits of the start and end program codes, and generates a signal indicative of a program mode when a start code is determined or when a program mode signal was generated in an immediately previous cycle and an end code is not determined.
  • a mode selector also includes a second logic circuit generating a wait signal whenever the start or end program codes are determined by the first logic circuit, and providing the wait signal to the buffer isolation gates so that any gate corresponding to a bit position of the shift buffer containing a bit corresponding to the start or end program codes is disabled.
  • the control circuit may include a memory to receive and store program information for the bitstream parser and to receive and store the one or more bits of new program information, and to reprogram the stored program information when the new program information is received by the control circuit, as well as an instruction decoder circuit to retrieve program information from the memory and generating the one or more parsing signals based on the retrieved program information.
  • control circuit also includes a program counter to generate addresses of storage locations in the memory to retrieve program information whenever the wait signal is not generated.
  • the control circuit may generate a wait value signal, where the logic circuit is responsive to the wait value signal in generating the wait signal .
  • the instruction decoder can be connected to the mode selector to receive the mode signal, and to the buffer to receive new programming information, where one or more bits of the bitstream segment representing such programming information are stored in the memory only when the instruction decoder receives the program mode signal.
  • the instruction decoder circuit may also beneficially be linked to the data memory to retrieve previously processed data, where instruction decoder generates one or more parsing signals based on both retrieved program information and attributes of the retrieved data.
  • the present invention also provides a method for parsing a digital bitstream having both data information and programming information.
  • the method requires receiving a segment of the digital bitstream in successive cycles; determining whether one or more bits of the received bitstream segment represents a mode selection code, where the mode selection code can be a data mode selection code or a program mode selection code; selecting a data mode when the data mode selection code is determined and a program mode when the program mode selection code is determined; storing one or more bits of the bitstream portion as new programming information when the program mode is selected; generating one or more parsing signals based on the stored programming information when the data mode is selected; and parsing the received bitstream in accordance with the generated parsing signals.
  • mode selection code can be a data mode selection code or a program mode selection code
  • selecting a data mode when the data mode selection code is determined and a program mode when the program mode selection code is determined
  • storing one or more bits of the bitstream portion as new programming information when the program mode is selected
  • the selecting step includes comparing the one or more received bits to the data and program mode selection codes, generating a signal indicative of a program mode when a program mode selection code is determined, or when a program mode signal was generated in an immediately previous cycle and a data mode selection code is not determined, generating a wait signal whenever either mode selection code is determined, and isolating one or more bits of the received bitstream portion which correspond to either mode selection code.
  • the parsing signal generation step advantageously provides for determining addresses of a program memory where command instructions are stored, retrieving such command instructions from the stored programming information in the program memory, and generating the one or more parsing signals based on the retrieved command instructions whenever a wait signal is not generated.
  • the method When parsed data is provided to a data memory, the method also provides for the retrieving of preselected data from the data memory, determining addresses of the program memory where command instructions are stored, retrieving the command instructions from the stored program information in the program memory, and generating one or more parsing signals based on both the retrieved command instructions and the retrieved data.
  • FIG. 1 is a system diagram of a programmable bitstream parser in accordance with the present invention
  • Fig. 2 shows a parser mode selection circuit useful in the Fig. 1 parser
  • Fig. 3 shows a control circuit useful in the Fig. 1 parser
  • Fig. 4 shows a data extraction unit useful in the Fig. 1 parser
  • Fig. 5 shows a instruction decoder useful in the Fig. 3 control circuit.
  • the parser 100 is designed to read data from a bitstream, parse the data into semantically meaningful segments, and store the parsed data in appropriate memory positions in a data RAM 150.
  • the bitstream may include both data and programming information, and should be delivered to the parser 100 in a serial fashion, i.e., one bit at a time at fixed time intervals.
  • the parser 100 includes shift buffer 110, buffer gates 120, parser mode selector 200, control 300, and data processor 400.
  • the parser 100 is synchronous, and its components are controlled by a common system clock (not shown) .
  • a common system clock not shown
  • parser 100 could be adapted to handle bitstream segments of other widths, e.g. 128 bits, or to parse such bitstream segments into words of any length, e.g., 16, 32, or 64 bits.
  • the size of the shift buffer 110 should be chosen so that it is capable of storing the largest parsable entity of the bitstream syntax, which is a design parameter.
  • the buffer can store a 64 bit wide segment from the incoming bitstream.
  • Buffer 110 includes 64 parallel outputs 111, one for each bit of the bitstream segment which is stores at any given time.
  • Each parallel output 111 of buffer 110 is connected to a buffer isolation gate 120.
  • the isolation gates 120 whose operation will be described in further detail below, are used to block or isolate certain bits stored in buffer 110 before the stored information is passed on to data processor 400 via data bus 121 or to control 300 via data bus 122.
  • the parser can be in either a data (D) mode or a program (P) mode.
  • D mode the bitstream segment stored in buffer 110 represents data.
  • the data is parsed by data processor 400 into 8 bit words which are subsequently placed in memory locations in RAM 150 via data bus 401.
  • Control 300 provides address locations to RAM 150 via address bus 503, and enables writing to the RAM 150 via read/write enable line 504.
  • P mode at least a portion of the bitstream segment stored in buffer 110 represents binary commands or instructions that indicate a reconfiguration of the syntax for subsequent data in the bitstream.
  • the binary commands or instructions are loaded directly into control 300 in order to reprogram the parser 100. The details of this operation are discussed below.
  • the parser mode selector 200 determines which mode the parser 100 should be in. Referring to Fig. 2, a preferred arrangement of the mode selector 200, buffer 110 and gate structure 120 are shown in greater detail. In the embodiment show in Fig. 2, the D mode is a default mode, with the P mode being triggered by a special binary codeword (command code) included in the bitstream called P_START, and turned off with another special binary codeword called P_END. Exemplary values for all special command codes can be found in the Appendix.
  • logical circuitry in mode selector 200 checks the bitstream segment stored in buffer 110 for the presence of these special command codes and switches the parser mode when necessary.
  • Control register 260 is an 8-bit register that stores pertinent state information needed for the coordination of the parser's operations.
  • shift buffer 110 reads 64 bits from the bitstream and shifts its contents to the right.
  • the 64 stored bits B are compared to the P_START and P_END codewords in comparators 210 and 220, respectively, which each perform a logical AND operation.
  • the outputs Al and A2 of comparators 210 and 220, respectively, are fed to logic cell 230, which also received the PF flag from register 260 from line 261.
  • Logic cell 230 performs the logical operation Al OR PF NAND A2 , to determine the new value of the flag PF.
  • the PF flag is set to 1 when P_START is encountered, and is reset to 0 when P_END is encountered; in all other cases it retains its previous value .
  • the P_START or P_END codes are necessary in order to determine whether the following bitstream segment represents data or programming information, the bits that represent the codes themselves are not otherwise useful to the parser, as they represent neither data nor programming information. Accordingly, when a P_START or P_END code detected, the bits which make up the code need to be isolated from the remainder of the parser. Bits that represent other codes which are discussed below must similarly be recognized and isolated.
  • the mode selector 200 includes logic which generates a input wait (IW) flag that is stored in control register 260.
  • the outputs Al and A2 of comparators 210 and 220, respectively, are fed to logic cell 240, which performs an OR operation, so that if either the P_START or P_END are present in the code, a signal indicative of the value of the P_START or P_END is placed on output line 241 logic cell 240.
  • Input stepping counter 250 receives the output of logic cell 240 to be set thereby.
  • a wait value In the case of other codes which need to be removed from the stored bitstream segment, a wait value
  • the wait value signal sets the counter to a numerical value equal to the number of bit positions required by the code (from 1 to 64) .
  • the input step counter 250 is 7-bits wide, to be able to handle up to and including 64 steps.
  • the counter 250 counts the number of bits held in buffer 110 that are to be isolated.
  • an IW flag is present in register 260, with the appropriate gate 120 receiving the IW flag via line 262.
  • the AND operation performed by the buffer isolation gates 120 effectively isolate the appropriate buffer 110 positions which store bits that represent the code.
  • control 300 When the counter 250 is set to a specific value, the parser 100 waits while an equal number of bits are inserted into the shift buffer from the input bitstream, while the isolated bits are shifted out. In this manner, bits which correspond to codes are removed, and only bits that represent data or programming information are passed through the gates 120 and on to the data processor 400 or control 300.
  • control 300 In order to properly parse the input bitstream, control 300 must store appropriate state information that will govern the sequence of steps that need to be taken by the data processor 400.
  • the control 300 can store information that controls the parsing of one or multiple parsable objects. Where more than one type of parsable object is present in a bitstream, the bitstream must include appropriate identification information in order for the control to determine which state information to use to parse the current object. Such information can be provided by special object identification codewords that immediately precede each object. The parser uses this information to determine which "program" to use for the current object.
  • control 300 includes program RAM 310, instruction decoder 500, program counter 320, additional counters 330 and 340, and multiplexer 350.
  • the command codes which control the operation of the parser are stored in program RAM 310, which in the embodiment shown in Fig. 3 can store codes as 8-bit words.
  • the control 300 sequences through the instructions stored in program RAM 310 in order to parse the bitstream. The sequencing is performed by a program counter (PC) 320, which supplies addresses to RAM 310 by address bus 506.
  • the PC 320 is reset by instruction decoder 500 whenever the mode selector 200 returns the parser to the D mode, and is advanced as each instruction is completed.
  • the advance of the PC is suspended by instruction decoder 500 when the input skip counter (SC) 250 is activated, as indicated by IW flag via line 262.
  • SC input skip counter
  • reset occurs only when the downloaded program affected the object currently being parsed by data processor 400, if any. This allows downloading of code while another object is being parsed.
  • the retrieved instruction is fed to the instruction decoder 500 via program RAM data bus 505.
  • the instruction decoder 500 determines how the next segment of data will be parsed, and how many input bits which represent object identification codewords should be discarded, i.e., the value loaded to the skip counter SC 501.
  • the instruction decoder will be described in further detail below.
  • instruction decoder 500 increments the PC 320 to obtain more data from program RAM 310 as appropriate.
  • a program instruction is terminated by the code END; the PC 320 is then reset to its original value so that parsing of the next object can commence.
  • control 300 When the mode selector 200 determines that the parser in the P mode, as indicated by the PF flag on line 261, the programming information contained in the incoming bitstream is utilized by control 300 as follows.
  • the P_START code recognized by the mode selector 200 is followed by an address in program RAM 310 where the programming information should be stored.
  • the address and programming information is received by control 300 via data bus 122 in exactly the same way as it should be stored in the program memory, which is controlled by the creator of the program prior to its insertion in the bitstream for downloading.
  • the control 100 only needs to transfer all bytes succeeding the P_START code (and the start address) to the specified program RAM address, stopping when it encounters the P_END code.
  • the PC is reset to the address where the program was loaded. If multiple object parsing is supported, then the reset occurs only if the downloaded code affected the object currently being parsed, if an object is being parsed by data processor 400.
  • data processor 400 includes a masking and sign extension unit 410 (MSU) , and a multiplexer 420.
  • MSU masking and sign extension unit 410
  • the MSU 410 receives the 64-bit wide bitstream segment from buffer 110 via data bus 121.
  • MSU 410 also receives 8 bits of command information, a sign extension signal 571, and an enabling signal 572 from the instruction decoder 500 via bus 502.
  • the command information which is stored in a Register A 510 of the instruction decoder 500, determines how may bits from the bitstream segment should be considered by the MSU 410; the remaining bits are discarded.
  • the five high order bits stored in Register 510 indicate the length of the parsed field, in bytes, minus 1, which is the result of an integer division by 8.
  • only the bits in positions 3-5 of register 510 are required for this purpose, since the largest parsable entity is 64 bits wide.
  • MUX 420 so that from one to eight bytes of data may be transferred to data RAM 150 via data bus 401.
  • the MSU when the MSU is enabled via line 571, it sign extends the bits which it is directed to use via the signal on line 572, and transfers single or multiple byte long objects to the data RAM 150 by way of the 8:1 MUX 420.
  • This data is stored in data RAM 150 at addresses which are determined by the instruction decoder, as explained below.
  • the instruction decoder 500 includes a set of registers 510, 520, 530, 540, 550, and 560, associated MUXs 511, 521, 555 and 565, a sequencer 570, and an arithmetic and logic unit 580.
  • the instruction decoder 500 is the coordinating circuit for the parser 100.
  • Sequencer 570 is a state machine that enables control signals at appropriate intervals according to the inputs which it receives. As shown in Fig.
  • the sequencer receives the above-discussed IW and PF flags from the mode selector 200 via lines 261 and 262, as well as programming information from the program RAM 310 via program RAM data bus 505, and new programming information from data bus 122 via MUX 521, register C 520, and output line 525.
  • the sequencer also provides a read/write enable signal to the external data RAM 150 via line 504, and controls the overall operation of the instruction decoder 500 by way of command lines (not shown) to each component listed above, as well as to MUX 350 and counters 320, 330 and 340 shown in Fig 3.
  • the parser when the parser is placed in the program mode, as indicated by the presence of the PF signal on line 261, the two bytes of information which immediately follow the P_START code are routed to the program counter 320 by data bus 122 and MUX 350.
  • the value stored in the program counter 320 represents the beginning address in program RAM 310 where new programming information is to be stored.
  • Subsequent bytes of information are not routed to the program counter 320, but instead are routed to register C 520 via MUX 521.
  • the first byte of information routed to register C is loaded into program RAM 310 via bus 505 at the address stored in program counter 320.
  • the program counter 330 is incremented by a control signal from the sequencer (not shown) , and the additional bytes of information are likewise stored in program RAM 310 at such incremented address locations.
  • the P_END code When the P_END code is encountered, the PF signal goes to 0, and the sequencer 570 resets the program counter 320. Normal data mode operations resume .
  • register C 520 In the data mode, programming information stored in the program RAM 310 are loaded into register C 520, with the number of bits of the current bitstream segment to be parsed is stored in register a 510.
  • Registers Dl and D2 530, 540 are used to obtain addresses from the program RAM 310 that are used in the case of indirect parsing representations .
  • Registers El and E2, 550, 560 are used to supply address values to the external data RAM 150 via address bus 503, so that parsed data can be stored in the data RAM 150 at an appropriate location.
  • the parser 100 can parse several different types of data syntax, including constant- length direct representation bit fields or "Fixed
  • FLCs Length Codes
  • variable length direct representation bit fields or "variable length FLCs, " which are FLC for which the length is determined by the context of the bitstream (i.e., another field that has previously appeared)
  • constant- length indirect representation bit fields which require an extra lookup into an appropriate table
  • variable-length indirect representation bit fields i.e., traditional Huffman codes.
  • An example is a 3-bit integer.
  • Table 1 depicts the command format, were PC indicates the starting address loaded into program counter 320.
  • the parser 100 when the parser 100 receives an object identification code which identifies the byte of data stored in program RAM 310 at the address PC, the command stored in RAM 310 at address PC is loaded into register C, informing the sequencer that a fixed-length code is to be parsed.
  • the sequencer 570 increments the program counter 320 by 1, thereby permitting the program counter to read the address in program RAM 310 which holds the length value for the corresponding object in the bitstream. This value is placed in register A via the program RAM's data bus 505 and MUX 511, and used by data processor 400 to properly parse the current bitstream segment, as discussed above .
  • Table 2 indicates various codes may be used to signify various types of fixed-length codes.
  • “expanded size” indicates the size of the parsed quantity after it is parsed.
  • Variable-length direct representation bit fields are similar to the constant-length ones, with a difference being that the size of the bit field is determined by a variable in the external data RAM 150, rather than in the program RAM 310. This allows an already parsed field to determine the length of a future field. An example is an integer whose length is determined by a field that has previously been parsed. Table 3 shows the command format of such codes.
  • the parser 100 when the parser 100 receives an object identification code which identifies the byte of data stored in program RAM 310 at the address PC, the command stored in RAM 310 at address PC is loaded into register C, informing the sequencer in this case that a variable-length FLC is to be parsed.
  • the sequencer 570 initiates two additional read cycles from the program RAM 310 in order to read the addrO and addrl bytes, which are temporarily stored in registers Dl and D2 530, 540.
  • the sequencer 570 then uses the values stored in registers Dl and D2 to address the external data RAM 150 via lines 535, 545, MUX'S 555 and 565, and address bus 503.
  • Indirect representation bit fields require the use of a table that maps the parsed input value to a set of actual values for the parsed parameter.
  • a parsed input having variable length is variable-length or Huffman code.
  • Such parsing tables are stored in a separate area of the program RAM 310. As shown in Table 5, a parsing table has one index column and one or more output columns (hence it defines a one-to-many mapping) , where each output column may have its own data type.
  • a map may stored in the program RAM 310 in the following manner. First, the length of the index column (in bits) is stored in the first byte, the number of value columns is stored in the second byte, and the number of bytes to skip to get at the index of the first row is stored in the third byte. The data type of each value is then stored in subsequent bytes using abstract, direct, or indirect representation codes.
  • the actual data is stored, one row at a time, including the index value; each value (except the index) is preceded by an "escape" byte, while the index is immediately followed by the number of bytes to skip in order to go to the representation of the next row (in order to facilitate quick jumps to subsequent rows without parsing the current one) .
  • Abstract representation codes are special codes that just indicate the type of data as stored in the map (CHAR, UCHAR, INT, UINT) .
  • the use of an escape byte allows the insertion of direct and indirect representations that substitute actual values, to thereby permit an extra degree of sophistication in the map: the map's functionality can be extended to include "escape" codes that trigger parsing of further data from the bitstream in order to obtain the value of the mapping.
  • An example of table mapping with an escape code is shown in Table 6.
  • the map indicated in Table 6 is stored in program RAM 310 as indicated in Table 7, where integer values require four bytes and word values require one byte .
  • the map indicated in Table 6 has an index that is one bit long (index values 0 and 1) , has two value columns, requires two bytes to be skipped to goto the index of the first row and has INT and CHAR data types .
  • the first index is 0, the row skip value is seven, the first escape byte is 0, the first data entry is 0, 0, 0, 42 (integer) , the second escape value is 0, the second data entry is 4 (character) , the second index value is 1, and so on.
  • each data value is preceded by its escape flag; the flag is set to one only before the element in position A+17, to trigger the escape to INT_D, 3. Accordingly, if the value 1 is encountered in the bitstream, then in order to obtain the value for the first column entry the parser will need to parse 3 subsequent bits from the bitstream. Such representation avoids the need to specify an INT_I plus the address, to indicate a variable length constant representation entry. Note that the escape types must be of the same type as the column they appear in.
  • the map type object identification code is indicated by a special code (MAP) stored in the program RAM 310, followed by the address where the map's description is stored.
  • MAP special code
  • the command format for such codes are depicted in Table 8.
  • the parser 100 when the parser 100 receives an object identification code which identifies the byte of data stored in program RAM 310 at the address PC, the command stored in RAM 310 at address PC is loaded into register C, informing the sequencer that a MAP type data format is to be parsed.
  • the sequencer 570 initiates two additional read cycles from the program RAM 310 in order to read the addrO and addrl bytes, which are temporarily stored in registers Dl and D2 530, 540.
  • the value in program counter 320 is shifted to counter 330, and the value in the registers Dl and D2 is shifted to the program counter 320.
  • next memory addresses i.e., the length of the index, the number of value columns, and the number of bytes to skip are retrieved and stored in register C 520, sequencer 570, and register A 510, respectively.
  • the program counter 320 indicates the address of the first data type; this value is stored in the extra counter 340 for possible use if a match is found.
  • the number of bytes to skip, stored in register A 510 is added to the value held in the program counter 320 to indicate the address of the first index, which is loaded into Register A and compared by ALU 580 with the input. If there is no match, the next program data byte is read in order to jump to the next index.
  • the sequencer 570 increments the program counter 320 by one, to bypass the skip byte address, and sends a wait value flag via line 501 to the mode selector 200 so that the shift buffer 110 is shifted by the number of bits indicated in register C.
  • the new address indicated by program counter 320 corresponds to the escape flag, which is loaded into register C 520. If the value loaded into register C is non-zero, the command that immediately follows is executed, and there is no need to use the value previously stored in the counter 340.
  • the sequencer exchanges the values stored in counters 320 and 340, thereby placing the address of the data type previously stored in counter 340 into counter 320 in order to retrieve the data type from the program RAM 310.
  • This value is stored in register C 520.
  • the values stored in counters 320 and 340 are then again swapped, to return the value held by program counter 320 to indicate a data address.
  • the data at this address is retreived from program RAM 310 and placed into register A.
  • the values stored in registers 320 and 340 are again exchanged, and the sequencer proceeds to locate the instruction for the second field. This process is continued until all MAP columns entries are exhausted.
  • Variable length indirect representation bit fields differ from their constant-length counterparts in that the length of the index column is not fixed.
  • the map show in Table 6 could be modified as shown in Table 9:
  • the notation 'Ob' is used to denote a binary number (similar to x 0x' for hexadecimal). As shown in Table 9, the index values have different lengths (1 and 2) . This is a very common situation in actual audio and video encoders, and allows for a reduction of the average number of bits necessary to represent a given quantity if the values are not equiprobable, so that more probable values are assigned shorter indices.
  • the map format described above can be used to store such information in the program RAM 310; modifications are necessary, however, in order to account for the varying index size.
  • the storage of the table is modified by storing the number of value columns is in the first byte, and the number of bytes to skip to get at the index of the first row in the third byte, with the data type of each value being stored in subsequent bytes using abstract, direct, or indirect representation codes.
  • the actual data is stored, one row at a time, including the index value preceded by its length. Each value, except the index, is preceded by an escape byte. The index is followed by the number of bytes to skip to go to the representation of the next row, thus permitting quick jumps between rows without additional parsing.
  • the map of Table 9 would have an in- memory representation as illustrated in Table 10.
  • VMAP The command code used to trigger variable-length indirect representation bit fields is VMAP, which is followed by the address of the program description in the program RAM.
  • Table 11 shows the format of variable-length indirect representation bit fields.
  • Example 5 General arithmetic and flow control .
  • bitstream syntax may be controlled by context, with the presence of a field being determined by the value of an already parsed parameter. Similarly, the number of fields present may be controlled by some parameter. This dependence may also not be direct, in the sense that the actual value may be an expression involving bitstream parameters and not the value of any specific parameter.
  • the instruction decoder 500 includes a general purpose arithmetic and logic unit (ALU) 580. The commands listed in Table 12 are supported by ALU 580.
  • ALU's accumulator i.e., register A 510
  • RAM[x] denotes the contents of external data RAM 150 at address % x'
  • addr' is a two byte entity that addresses the data RAM via registers Dl and D2 530, 540.
  • the instruction decoder 500 can implement all different types of for and while loops, as well as general expression evaluation.
  • the ALU 580 can be any off-the shelf unit which uses 2's complement arithmetic, and does not require a stack, a stack pointer or a "return" instruction.
  • the present invention has particular applicability to object-based compression techniques such as the MPEG-4 standardization effort by the ISO/IEC JTC1/SC29/WG11 group, which permits a variable bitstream sytax, as well as to any generic digital bitstream which has a varying syntactic configuration.
  • the present invention provides both for programmability of the parser as well as for the separation of the bitstream parsing process from bitstream processing.
  • the parser can be programmed by the incoming bitstream in three general ways. First, the parser can be programmed to recognize certain high-level object identifiers (e.g., slices or tools, which may be tagged to the bitstream during encoding) and to redefine such objects during parsing. Second, the parser can be programmed to recognize certain context-sensitive objects, i.e., objects that require the presence of other objects to be recognizable (an "if then else" object description) .
  • the parser can be programmed to recognize certain repetitive objects and to apply the same syntax to parse the repetitive bitstream until some condition is met (a "for while do" object description) . Accordingly, those skilled in the art will appreciate that the foregoing description presents a bitstream parsing technique that is fully adaptable to the syntax used in a digital bitstream without the requirement of interrupting the parsing operation to reprogram the bitstream parser every time a new syntax is encountered.
  • the parser 100 is designed to accept a serial bitstream
  • parallel input can also be accommodated, e.g., when the information is provided one byte at a time, simply by adding a parallel-to- serial converter using a shift buffer with parallel loading.
  • the mode selector described above is designed to compare the incoming bitstream to a P_START code and a P_END code, the logic of the mode selector 200 could be easily modified to handle other bitstream codes which may indicate the arrival of programming or data information.
  • the described embodiment uses a special program RAM 310 to store command information, it is also possible to use the external data RAM 150 for the same purpose.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • General Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Health & Medical Sciences (AREA)
  • Artificial Intelligence (AREA)
  • Audiology, Speech & Language Pathology (AREA)
  • Computational Linguistics (AREA)
  • General Health & Medical Sciences (AREA)
  • Software Systems (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)

Abstract

L'invention concerne un analyseur (100) servant à analyser un train binaire numérique comprenant des informations de données et des informations de programmation, sur la base des informations de programmation contenues dans le train binaire. Cet analyseur (100) comprend un tampon (110), un sélecteur de mode (200), un circuit de commande (300) et un processeur de données (400). Le sélecteur de mode (200) détermine si au moins un bit du segment de train binaire représente un code de sélection de mode, et sélectionne un mode d'analyseur en réponse au code de sélection de mode. Le circuit de commande (300) reçoit et stocke les bits provenant du tampon lorsque l'analyseur de train binaire (100) est en mode programme afin de reprogrammer le circuit de commande (300) avec des informations de programme reçues récemment, et utilise les informations de programme pour produire au moins un signal d'analyse lorsque l'analyseur de train binaire (100) est en mode données. Le processeur de données (400) reçoit des bits du tampon (110) et analyse des signaux provenant du circuit de commande (300) lorsque l'analyseur de train binaire (100) est en mode données, et analyse les bits reçus en fonction des signaux d'analyse.
PCT/US1996/017876 1996-11-08 1996-11-08 Procedes et dispositif pour analyseur de train binaire programmable destine a des systemes audiovisuels et de decodage generique Ceased WO1998021889A1 (fr)

Priority Applications (2)

Application Number Priority Date Filing Date Title
PCT/US1996/017876 WO1998021889A1 (fr) 1996-11-08 1996-11-08 Procedes et dispositif pour analyseur de train binaire programmable destine a des systemes audiovisuels et de decodage generique
US09/297,714 US6512775B1 (en) 1996-11-08 1996-11-08 Method and apparatus for a programmable bitstream parser for audiovisual and generic decoding systems

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/US1996/017876 WO1998021889A1 (fr) 1996-11-08 1996-11-08 Procedes et dispositif pour analyseur de train binaire programmable destine a des systemes audiovisuels et de decodage generique

Publications (1)

Publication Number Publication Date
WO1998021889A1 true WO1998021889A1 (fr) 1998-05-22

Family

ID=22256101

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/US1996/017876 Ceased WO1998021889A1 (fr) 1996-11-08 1996-11-08 Procedes et dispositif pour analyseur de train binaire programmable destine a des systemes audiovisuels et de decodage generique

Country Status (1)

Country Link
WO (1) WO1998021889A1 (fr)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8521898B2 (en) 2000-10-20 2013-08-27 Robert Bosch Gmbh Method for structuring a bitstream for binary multimedia descriptions and a method for parsing this bitstream

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5452006A (en) * 1993-10-25 1995-09-19 Lsi Logic Corporation Two-part synchronization scheme for digital video decoders
US5532744A (en) * 1994-08-22 1996-07-02 Philips Electronics North America Corporation Method and apparatus for decoding digital video using parallel processing
US5559999A (en) * 1994-09-09 1996-09-24 Lsi Logic Corporation MPEG decoding system including tag list for associating presentation time stamps with encoded data units
US5566089A (en) * 1994-10-26 1996-10-15 General Instrument Corporation Of Delaware Syntax parser for a video decompression processor
US5570197A (en) * 1993-06-01 1996-10-29 Matsushita Electric Industrial Co., Ltd. Apparatus for further compressing and recording encoded digital video data streams

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5570197A (en) * 1993-06-01 1996-10-29 Matsushita Electric Industrial Co., Ltd. Apparatus for further compressing and recording encoded digital video data streams
US5452006A (en) * 1993-10-25 1995-09-19 Lsi Logic Corporation Two-part synchronization scheme for digital video decoders
US5532744A (en) * 1994-08-22 1996-07-02 Philips Electronics North America Corporation Method and apparatus for decoding digital video using parallel processing
US5559999A (en) * 1994-09-09 1996-09-24 Lsi Logic Corporation MPEG decoding system including tag list for associating presentation time stamps with encoded data units
US5566089A (en) * 1994-10-26 1996-10-15 General Instrument Corporation Of Delaware Syntax parser for a video decompression processor

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8521898B2 (en) 2000-10-20 2013-08-27 Robert Bosch Gmbh Method for structuring a bitstream for binary multimedia descriptions and a method for parsing this bitstream

Similar Documents

Publication Publication Date Title
US6512775B1 (en) Method and apparatus for a programmable bitstream parser for audiovisual and generic decoding systems
US5990812A (en) Universally programmable variable length decoder
EP0129439B1 (fr) Appareil et méthode de compression et de décompression à grande vitesse de données
US6246347B1 (en) Controller for a variable length decoder
KR100286195B1 (ko) 가변장 코드로 엔코드된 신호의 디코딩 장치
JP2915568B2 (ja) テープドライブシステムのための適応データ圧縮装置
JPH0368219A (ja) データ圧縮装置及び方法
JP3341962B2 (ja) 可変長復号器及び可変長符号値を復号化する方法
US6310563B1 (en) Method and apparatus for enhanced decompressor parsing
US5594437A (en) Circuit and method of unpacking a serial bitstream
WO2001056168A1 (fr) Compression de donnees plus efficace
EP0582907A2 (fr) Dispositif et méthode de compression de données utilisant la recherche par comparaison de chaînes et le codage de Huffman
CA2131823A1 (fr) Methode de compression de donnees a algorithme de codage ameliore utilisant une technique d'empilage de jetons
US5940016A (en) Syntax parser for a MPEG2 video decoder
US6653953B2 (en) Variable length coding packing architecture
US5555323A (en) System for bi-level symbol coding/decoding with saved storage and method for same
EP1636997A1 (fr) Procede et systeme de decodage de signaux a codage a longueur variable, produit de programme informatique correspondant
GB2333000A (en) Finite state machine coding of information
EP0576131B1 (fr) Décodage de données sérielles
EP0079442B1 (fr) Appareil de traduction de données traduisant entre des formes de données codées brutes et comprimées
WO1998021889A1 (fr) Procedes et dispositif pour analyseur de train binaire programmable destine a des systemes audiovisuels et de decodage generique
KR20010075681A (ko) 프로세싱 시스템에서의 실행 인스트럭션 형성 방법
US8599841B1 (en) Multi-format bitstream decoding engine
WO1999052294A1 (fr) Procede et appareil pour le codage/decodage d'un flux de donnees via les techniques inferentielles
JPH08251033A (ja) データ処理方法

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): CA JP KR US

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE CH DE DK ES FI FR GB GR IE IT LU MC NL PT SE

DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
121 Ep: the epo has been informed by wipo that ep was designated in this application
WWE Wipo information: entry into national phase

Ref document number: 09297714

Country of ref document: US

122 Ep: pct application non-entry in european phase
NENP Non-entry into the national phase

Ref country code: CA