AU760244B2 - Entropy decoding - Google Patents

Description

S&FRef: 564747

AUSTRALIA

PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT

ORIGINAL

Name and Address of Applicant: Actual Inventor(s): Address for Service: Canon Kabushiki Kaisha 30-2, Shimomaruko 3-chome, Ohta-ku Tokyo 146 Japan Dominic Yip Spruson Ferguson St Martins Tower,Level 31 Market Street Sydney NSW 2000 (CCN 3710000177) Invention Title: Entropy Decoding ASSOCIATED PROVISIONAL APPLICATION DETAILS [33] Country [31] Applic. No(s) AU PQ9826 [32] Application Date 01 Sep 2000 The-following statement is a full description of this invention, including the best method of performing it known to me/us:- 5815c ENTROPY DECODING Technical Field of the Invention The present invention relates generally to data decompression. In particular it relates to a method and apparatus for entropy decoding symbols.

Background Art A call for proposals for the new JPEG-2000 standard was recently issued and a draft standard has been published entitled "Information Technology JPEG 2000 Image coding System JPEG 2000 Committee Draft version 1.0, 9 December 1999".

This draft standard proposes that the whole image be divided into one or more image tile components, each of which are then 2-D discrete wavelet transformed. The transform coefficients of each image tile component are then grouped into sub-bands, which sub-bands are further partitioned into rectangular code blocks before each code block is then entropy encoded. The transform coefficients of each code block are expressed in a sign-magnitude representation prior to entropy coding. The entropy encoding consists of two parts: a context generator and an arithmetic coder. The arithmetic coder takes as input the bit symbol of a coefficient to be encoded and the context of that bit symbol. The context of a bit symbol of a coefficient, which bit symbol is to be coded by the arithmetic coder, is based on the 'significance' states of the 8 surrounding coefficients in the same bit-plane of the code block. The 'significance' state 20 of a coefficient is a binary-valued variable Si[m,n], which is initialised to 0, but ~transitions to 1 immediately after the coefficient's first non-zero bit value is encoded.

Fig. 1 shows the neighbouring significance states Si[m-l,n-1], Si[m-l,n] Si[m-l,n+l], Si[m,n-1] Si[m,n+l], Si[m+l,n-1], Si[m+l,n] and Si[m+l,n+l] of the 8 surrounding coefficients of a coefficient where m,n are the row and column numbers respectively of the code block and Si[] is the significance state immediately prior to the encoding of the bit symbol i of the coeficient These neighbouring significance states are sometimes referred to as the significance states of the 3x3 neighbourhood of the coefficient X[m,n].

564747.doc The arithmetic coder first codes all the bit symbols of the most significant bit-plane of a code block, then all the bit symbols of the next lower bit-plane of the code block and so on to the least significant bit-plane. Within each bit-plane of a code block, the arithmetic coder codes the bit symbols of the coefficients in three passes in a predetermined order.

The first pass of a bitplane is called the significance propagation pass (SP pass), the second pass of the bitplane is called the magnitude refinement pass (MR pass), and the third and last pass of the bitplane is called the cleanup pass (N pass). During the SP pass, a bit symbol of the bitplane is encoded if the bit symbol to be encoded has a neighbouring bit symbol, which has a significance state of one(l) but has itself a significance state of zero(0). During the MR pass, a bit symbol of the bitplane is encoded, if not already encoded, if the coefficient of that bit symbol is already significant in the previous encoded bitplane. During the N pass, the remaining bit symbols of the bitplane that have not already been encoded are then encoded. The significance propagation pass codes only bits of coefficients that were insignificant (the significant bit has yet to be encountered) and have a non-zero context. All other coefficients are skipped.

The context is delivered to the arithmetic coder along with the bit to be encoded and i' the encoded symbol is output to the bitstream. If the value of this bit symbol to be coded is one and the significance state is zero then the significance state is set to one (1) once the bit symbol is coded and the next immediate bit symbol to be coded is the sign bit for the coefficient. Otherwise, the significance state remains zero When the contexts of successive coefficients and passes are considered, the most current significance state for this coefficient is used.

The arithmetic coder codes the bit symbols of a bitplane in the three passes (SP, oee• MR, and N) in the same predetermined order. The arithmetic coder first proceeds to the highest bitplane that has a non-zero bit in it and skips the SP, MR passes and commences with the N pass. The arithmetic coder then proceeds to the next lower bit plane and codes the bit symbols in the three passes (SP, MR, and N) in that order. It then proceeds to the 564747.doc next lower bit plane and codes the bit symbols in the same order of passes (SP, MR, and N) and so on to the least significant bitplane. In addition, each bitplane of a code block is scanned in a particular order. Starting at the top left, the first four bit symbols of the column are scanned. Then the first four bit symbols of the second column, until the width of the code-block has been covered. Then the second four bit symbols of the first column are scanned and so on. A similar scan is continued for any leftover rows on the lowest code blocks in the sub-band. Fig. 2 shows an example of the code-block scan pattern for a code block having 64 transform coefficients arranged in an 8x8 block.

The entropy decoding described in the JPEG2000 draft standard is a mirror image of the entropy decoding. The entropy encoding also comprises two sections: a context generator and an arithmetic decoder. The arithmetic decoder takes as input the symbol to be decoded and the context of that symbol to be decoded. The context of a symbol to be decoded, which symbol is to be decoded by the arithmetic decoder, is based on the 'significance' states of the 8 surrounding coefficients in the same bit-plane of the code block. The 'significance' state of a coefficient is a binary-valued variable which is initialised to 0, but transitions to 1 when the coefficient's first non-zero bit-plane value is decoded. In this fashion, the significance states of the coefficients during the decoding phase mirrors the significance states of the coefficients during the encoding phase (see 2 Fig. 1).

The arithmetic decoder decodes the symbols in the same order that they were encoded. During decoding, the position of the next symbol to be decoded, and thus the context of the next symbol to be decoded sometimes depends on the current decoded symbol. This is especially true in the significance propagation phase. For instance, if the current decoded bit is subsequently found to be significant, then the next symbol to be 25 decoded is the sign bit of the current position. On the other hand, if the current decoded bit is subsequently found to be insignificant, then the position of the next symbol to be decoded is the next position in the scanning order that has an significance state of zero (0) and a surrounding significance state of one(l). Furthermore, if the current decoded bit is 564747.doc subsequently found to be significant, then the insignificant coefficients in the 3x3 neighbourhood of that decoded bit that follows in the scanning order also need to be decoded in the same signification propagation pass. This is illustrated with reference to Figs. 4A, 4B13, and 4C. As will be apparent, the order of the positions of the insignificant coefficients within the 3x3 neighbourhood that immediately follow the current position in the scanning order depend upon the location of the 3x3 neighbourhood within the code block. For instance, Fig. 4A shows the order of the positions in accordance with the scanning order, where the 3x3 neighbourhood falls entirely within rows (2-30), and (4-32) of the code block (see Fig. The significance state of the coefficient of the current position presently being decoded is denoted by C. The blank entries of the 3x3 neighbourhood are those positions where the corresponding symbols have already been scanned and decoded. In this example, if the current decoded bit associated with the centre coefficient C is subsequently found to be significant, then any insignificant symbols in positions 1, 2, 3 and 4 are also to be processed during the current significance propagation pass in scanning order. Fig. 4B shows the order of the positions in accordance with the scanning order, where the 3x3 neighbourhood falls within rows (4- 32), (33-61), and (34-62) of the code block (see Fig. Similarly, the significance state *.of the coefficient of the current position presently being decoded is denoted by C. Again, the blank entries of the 3x3 neighbourhood are those positions where the corresponding symbols have already been scanned and decoded. In this example, if the current decoded bit associated with the centre coefficient C is subsequently found to be significant, then any insignificant symbols in positions 1, 2, and 3 are also to be processed during the current significance propagation pass in scanning order. Fig. 4C shows the order of the positions in accordance with the scanning order, where the 3x3 neighbourhood falls 25 within rows and (33-61) of the code block (see Fig. Similarly, the significance state of the coefficient of the current position presently being decoded is denoted by C. Again, the blank entries of the 3x3 neighbourhood are those positions where the corresponding symbols have already been scanned and decoded. In this 564747.doc example, if the current decoded bit associated with the centre coefficient C is subsequently found to be significant, then any insignificant symbols in positions 1, 2, 3, 4, and 5 are also to be processed during the current significance propagation pass in scanning order.

Thus, in some circumstances the position and context of the next symbol to be decoded sometimes depends on the current decoded symbol. A somewhat similar situation occurs during the N pass. If the current decoded bit is subsequently found to be significant, then the next symbol to be decoded is the sign bit of the current position. On the other hand, if the current decoded bit is subsequently found to be insignificant, then the next symbol to be decoded is the next symbol in the normalisation pass.

A prior art JPEG2000 entropy decoder has been proposed, which consists of 2 sections: context generation and arithmetic decoding. In the proposed prior art entropy decoder, the arithmetic decoder first decodes the current symbol to be decoded, and then the context generator section generates the context of the next symbol to be decoded, utilising the current decoded symbol. This is illustrated with reference to Figs 3A and 3B.

Fig. 3A shows the timing diagram of the proposed prior art arithmetic decoder. Fig. 3B shows the timing diagram of the proposed context generator to be used in conjunction 9 with the arithmetic decoder of Fig. 3A. In this proposed prior art arithmetic decoder, the symbol n to be decoded is input at time 308 to the decoder together with its context n, 20 which was previously output by the context generator at time 320. The proposed prior art arithmetic decoder takes the cycle 308 to 310 to decode the nth symbol, which decoded symbol is then output and fed at time 316 to the proposed prior art context generator. The :9 **proposed prior art context generator then takes the cycle 316 to 318 to determine the context of the next symbol n+l to be decoded. The symbol n+l to be decoded is then 25 input at time 312 to the proposed prior art arithmetic decoder together with its context n+l, which was previously output by the context generator at time 318. The proposed prior art arithmetic decoder takes the cycle 312 to 314 to decode the n+lth symbol, which 4U S 564747.doc

FI

is then output and fed at time 322 to the proposed prior art context generator. The proposed prior art entropy decoder takes the time periods 312-314 and 316-318 to decode the nth symbol. However, the proposed prior art entropy decoder suffers from the disadvantage of having slow throughput.

Summary of the Invention It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements and/or proposals.

According to a first aspect of the invention, there is provided a method for entropy decoding symbols, the method simultaneously performing a first set of one or more steps and a second set of one or more steps, wherein said first set comprises the step of: entropy decoding a current symbol to be decoded using said current symbol to be decoded and a current context; and said second set comprises the steps of: determining a first context; determining a second context; and selecting one of the determined contexts as the next current context based on the current decoded symbol; repeating the first and second sets of steps for the next symbols to be decoded in turn.

According to a second aspect of the invention, there is provided a method for S entropy decoding symbols, the method simultaneously performing a first set of one or more steps and a second set of one or more steps if a current context was generated in accordance with a first predetermined mode of operation and the method simultaneously performing a third set of one or more steps and fourth set of one or more steps if the current context was generated in accordance with a second predetermined mode of operation, wherein said first set comprises the step of: entropy decoding a current symbol to be decoded using said current symbol to be decoded and a current context, wherein said current context was previously generated in accordance with said first predetermined mode of operation; and said second set comprises the steps of: determining a first context in accordance with said first predetermined mode of operation; determining a second context in accordance with said second predetermined mode of operation; and selecting one of the generated contexts as the next current context based on the current decoded 564747.doc symbol; and said third set comprises the step of: entropy decoding a current symbol to be decoded using said current symbol to be decoded and a current context, wherein said current context was previously generated in accordance with the second predetermined mode of operation; and said fourth set comprises the steps of: determining a third context in accordance with the first predetermined mode of operation; and selecting the third context as the next current context based on the current decoded symbol; and repeating the first and second set of steps or the third and fourth set of steps for the next symbols to be decoded in turn.

According to a third aspect of the invention, there is provided apparatus for entropy decoding symbols, the apparatus comprising: an entropy decoder for entropy decoding a current symbol to be decoded having as input said current symbol to be decoded and a current context; a context generator for generating a first context in accordance with a first predetermined mode of operation; a context generator for generating a second context in accordance with a first predetermined mode of operation; and a selector for selecting one of the generated contexts as the next current context of the next symbol to be decoded based on the current decoded symbol.

S•Brief Description of the Drawings A number of preferred embodiments of the present invention will now be described with reference to the drawings, in which: Fig. 1 shows the neighbouring significance states of the 8 surrounding coefficients of a coefficient utilised in the prior art JPEG2000 draft standard; Fig. 2 is a schematic block diagram illustrating an example of the code-block scan pattern for a code block utilised in the prior art JPEG2000 draft standard; Fig. 3A illustrates the timing diagram of a proposed prior art arithmetic decoder, Fig. 3B illustrates the timing diagram of a proposed prior art context generator to be used in conjunction with the proposed prior art arithmetic decoder of Fig. 3A; Fig. 3C illustrates the timing diagram of the arithmetic decoder in accordance with the preferred embodiment; 564747.doc Fig. 3D illustrates the timing diagram of the context generator in accordance with the preferred embodiment; Fig. 4A is a schematic block diagram of a centre coefficient and its 3x3 neighbourhood for illustrating the prior art JPEG2000 standard; Fig. 4B is another schematic block diagram of a centre coefficient and its 3x3 neighbourhood for illustrating the prior art JPEG2000 standard; Fig. 4C is another schematic block diagram of a centre coefficient and its 3x3 neighbourhood for illustrating the prior art JPEG2000 standard; Fig. 5 is a schematic block diagram of an entropy decoder in accordance with a preferred embodiment; Figs. 6(a) and 6(b) is a flow chart of a sub-procedure for use in a method for entropy decoding symbols in accordance with a preferred embodiment; Fig. 7 is a Table showing the relationship between the context states and the neighbours h, v, and d, during the zero coding mode; Fig. 8 is a schematic block diagram of the logic circuitry of the context generation S:logic device of Fig. 5 for looking up the context states during the zero coding mode.

Fig. 9 is a Table showing the relationship between two variables h, v and the significance and sign of neighbours A and B during the sign encoding mode; 10 is a Table showing the relationship between the variables h, v and X and the context states during the sign encoding mode; Fig. 11 is a schematic block diagram of the logic circuitry of the context generation logic device of Fig. 5 for looking up the context states during the sign coding mode; and Fig. 12 is a schematic block diagram of the organisation of the list memory of Fig. Detailed Description including Best Mode Where reference is made in any one or more of the accompanying drawings to steps and/or features, which have the same reference numerals, those steps and/or features have 564747.doc for the purposes of this description the same function(s) or operation(s), unless the contrary intention appears.

The principles of the preferred apparatus and method described herein have general applicability to data decompression. However, for ease of explanation, the preferred apparatus and method are described with reference to digital image decompression in accordance with the above mentioned JPEG 2000 draft standard. However, it is not intended that the present invention be limited to the described apparatus and method. For example, the invention may have application to digital video decompression.

Before proceeding with a detailed description of the preferred apparatus and method, a brief overview of the preferred method and apparatus will now be described.

The following preferred embodiments are limited to a method and apparatus for decoding symbols during a significance propagation pass according to the draft JPEG2000 standard. However, the present invention is not limited to the described apparatus and method. The invention also has application to decoding symbols during a cleanup pass according to the draft JPEG2000 standard. As will be apparent to a man skilled in the art, the following embodiments may be modified to implement the cleanup pass according to the JPEG2000 draft standard without departing from the spirit and scope of the invention.

As mentioned previously, during the significance propagation pass (SP pass) of the draft JPEG2000 decoding, the position of the next symbol to be decoded, and thus the 20 context of the next symbol to be decoded sometimes depends on the current decoded .oo.oi symbol. For instance, during the significance propagation pass if the current symbol to be decoded is subsequently found to be significant, then the next symbol to be decoded is the sign bit of the current position. If however, the current symbol to be decoded was found to be insignificant then the next symbol to be decoded is the next in the significance propagation pass. Furthermore, if the previously decoded symbol was significant (ie the current symbol to be decoded is a sign bit), then the next symbol to be decoded is the next in the significance propagation pass.

564747.doc In the preferred method and apparatus the next symbol to be decoded during the SP pass is either one of the following: 1. The sign bit of the current symbol to be decoded (let this be symbol or 2. The symbol corresponding to the first position in a list of positions of the symbols to be decoded during the current significance propagation pass immediately following the position of the current symbol to be decoded (let this be symbol This significance propagation list (SP list) is generated by previous known significance information about all the symbols and is updated just prior to the decoding of the current symbol. The manner in which this list is generated and maintained is described in more detail below.

The preferred method and apparatus switch between two modes of operation. The preferred method and apparatus operate in a first mode where the last decoded symbol was found to be insignificant. During the first mode, the preferred method and apparatus decode the current symbol at the same time as generating the contexts for both the next symbols (A and Once the current symbol is finally decoded, one of the contexts of symbols (A or B) may be selected as the context of the next symbol (A or B) to be decoded depending on the current decoded symbol. The following rules are utilised to decide which symbol or B) is to be decoded next, and which context of the next symbol (A or B) should be selected: oooi If the current decoded symbol is insignificant, then symbol B is the next symbol to 20 be decoded and its context should be selected.

.ooooi S. If the current decoded symbol is significant, then symbol A is the next symbol to be decoded and its context should be selected.

The preferred apparatus and method operate in a second mode where the previously decoded symbol was found to be significant (ie the current symbol to be decoded is a sign 25 bit). During the second mode, the preferred method and apparatus decode the current symbol at the same time as generating the context for the next symbol to be decoded.

In this second mode, symbol is to be decoded next.

564747.doc -11- Turning now to Fig. 3C, there is illustrated the timing diagram of an arithmetic decoder in accordance with the preferred embodiment. Also, Fig. 3D illustrates the timing diagram of a context generator in accordance with the preferred embodiment run concurrently with preferred arithmetic decoder of Fig. 3C. The preferred entropy decoder consists of two sections: a context generator and an arithmetic decoder. The arithmetic decoder takes as its input the symbol to be decoded and its context. A symbol n and its context are input at time 300 to the preferred arithmetic decoder. The preferred arithmetic decoder takes the period 300-302 to decode the nth symbol, which is output at time 302 and fed to the context generator at time 308. If the mode of operation was a first mode, then whilst the nth symbol is presently being decoded, the contexts of both the next symbols (A and B) to be decoded are determined during the period 304-308. The context generator selects the context of the next symbol (A or B) depending upon the output of the nth symbol during the period 308-306 and outputs this next context at time 306. The next symbol (A or B) and its context are input at time 310 to the preferred arithmetic decoder. On the other hand, if the mode of operation was a second mode, then whilst the nth symbol is presently being decoded, the context of the next symbol to be decoded are determined during the period 308-306. The next symbol and its context are input at time 310 to the preferred arithmetic decoder.

ooo• do In this way, it is possible to maximise the throughput of the preferred entropy decoder. Namely, the preferred context generator and preferred arithmetic decoder perform their operations substantially simultaneously. On the other hand, the proposed prior art entropy decoder alternatively performs the operations of the arithmetic decoder and context generator. These timing diagrams (Fig. 3C and 3D) of the preferred entropy decoder are basic timing diagrams and are for illustrative purposes only. The actual 25 timing diagrams may vary depending upon the exact circuit structure of the preferred arithmetic decoder and context generator. For instance, the period for determining the context of the symbol may be shorter than the period for decoding a symbol. In this case, the preferred context generator will have a waiting period between cycles of operation.

564747.doc -12- Notwithstanding, the throughput is still maximised in that there is still overlap in the concurrent operations of the preferred arithmetic decoder and the context generator.

Turning now to Fig. 5, there is shown a schematic block diagram of an entropy decoder 500 in accordance with a preferred embodiment. The arithmetic decoder 520 takes as input the current symbol to be decoded 550 and its context 552. The arithmetic decoder 520 may be any suitable known arithmetic decoder, such as that described in the above mentioned draft standard. The arithmetic decoder 520 then outputs the currently decoded symbol 554 to the next stage 522 in the decompression stage (not shown) and also feds 554 back this as input to the context generator. Namely, the arithmetic decoder 520 feds back the currently decoded symbol 554 to the Significance Table Organiser (STO) 501 of the context generator.

The entropy decoder 500 is able to operate in two modes. The entropy decoder 500 operates in a first mode where the previous decoded symbol 554 was found to be insignificant. The entropy decoder operates in a second mode where the previously decoded symbol 554 was found to be significant (ie the current symbol to be decoded is a sign bit).

•During the first mode, the List Memory Manager LMM 510 feeds to the STO 501 the location 556 in the code block of the symbol that is currently being decoded. The STO 501 receives the position 556 in the code block of the symbol that is currently being decoded by the decoder 520 prior to the completion of its actually being decoded by the decoder 520. In response to receiving this position 556, the STO 501 fetches from the Significance Table Memory 502 the significance states of the coefficients in the 3x3 neighbourhood surrounding the current position 556 and feeds 560 that to the context generator logic 506. The context generation logic device 506 generates the context S 25 state 562 according to a sign coding mode based on the significance of the neighbourhood of the current position. The context generator 506 outputs the expected sign bit of the current location in the code block, together with the associated context 562 of this sign 564747.doc -13bit. The context generation logic device 506 is also formed from logic circuitry as will be described in more detail below.

At the same time, the LMM 510 uses the location 556 of the symbol currently being decoded to fetch the next position in a Significance Propagation list stored in the List Memory 512, and feeds 564 that to STO 501. The List Memory 512 contains three lists: a Significance Propagation list; a Magnitude Refinement list; and a Cleanup list, which will be described in more detail below. The STO 501 uses that next position to fetch the significance states from the Significance Table Memory 502 of the symbols in the 3x3 neighbourhood around that next position in the Significance Propagation list. The STO returns that information 566 back to LMM 510, which in turn feeds 568 that to the context generation logic device 508. The context generation logic device 508 generates the context state 570 in accordance with a zero coding mode based on the significance of that neighbourhood. The context generator 508 outputs the generated context 570 of this next position in the Significant Propagation List.

When the next decoded bit 554 eventually arrives at the context selector 514, it is used to select which context to feed into the arithmetic decoder 520. The context selector 514 selects one of these generated contexts 562 and 570 in accordance with the rules mentioned above. These rules utilise the significance of the decoded bit to determine which context to select. Preferably, these rules are implemented in the context selector 514 in the form of logic circuitry.

The STO 501 also updates the significance of that decoded symbol 554 if required.

This is achieved in the following manner. If the decoded symbol 554 received by the STO 501 is a zero then the STO 501 does not update the Significance table 502. On the other hand, if the decoded symbol is a one then the significance state currently S 25 stored at the current position in the table 502 is updated by the STO 501 to one :The LMM 510 upon finally receiving 554 the decoded symbol determines if is significant and updates the Significance Propagation list. If so, the LMM 510 determines if there are any currently surrounding insignificant neighbours in the 3x3 neighbourhood 564747.doc -14of the position of that decoded symbol. The LMM 510 deletes these insignificant neighbours from the cleanup list and adds these insignificant neighbours to the SP list (if not already on the list). The LMM 510 then re-indexes the SP list in accordance with the scanning order.

During the second mode, the entropy decoder 500 operates similar to the first mode except that context generator 506 is made inoperable and does not supply a context to the context selector 562. Moreover the context selector 514 automatically selects the context generated by the context generator 508 for supply to the arithmetic decoder.

The context generation logic devices (506 and 508) will now be described in more detail. The context generation logic device 508 accepts the significance states of the coefficients in the 3x3 neighbourhood of the coefficient being coded, and generates the context for the arithmetic coder. Also, it accepts mode signals that indicate which type of context it should generate. Preferably, the context generation logic device 508 is able to operate in a number of different modes. In particular, the context generation logic may operate in a zero coding mode, run-length coding and magnitude refinement mode.

Preferably, the context generation logic device 506 operates solely in a sign coding mode.

go o The zero coding mode and sign coding mode are used in both the significance

S..

s propagation and cleanup passes. The magnitude refinement mode is used during the magnitude refinement pass. The cleanup pass can also use run-length coding. The context generation logic device 508 can be modified to include other modes of operations .g..oi if so desired. The following describes how the context generation logic devices 508 0505 and 506 operate in the zero coding and sign coding modes respectively.

The context generation logic device 508 generates during the zero coding mode one of 9 different context states based on how many and which ones of the eight immediate °S 25 neighbours of the current 3x3 neighbourhood 568 are significant (see Fig. The *see seesmapping also depends on which sub-band at a given decomposition level) the current code block is in. These neighbours are grouped into three categories: immediate horizontal neighbours 564747.doc immediate vertical neighbours immediate diagonal neighbours (d) The immediate neighbours that lie beyond the boundary of the code block are taken as being insignificant when forming contexts in accordance with the draft JPEG 2000 standard.

Turning now to Fig. 7, there is illustrated a table, which shows the relationship between the 9 context states and the 3 quantities, h, v, and d, for each type of sub-band during the zero coding mode. The context labels are numbered only for identification.

The actual identifiers used is a matter of implementation. The reference x indicates that this quantity is not taken into account in determining the context state. The context generation logic device 508 generates during zero coding the context state in accordance with the table shown in Fig. 7. For example, if the current code block is in the LL subband and the current 3x3 neighbourhood has two significant horizontal neighbours then the context state is 8.

Turning now to Fig. 8, there is shown a schematic block diagram of the logic 9.

circuitry of the context generation logic device 508 for looking up the context states during the zero coding mode. In operation, the significance states S1, S2, S3, S 4

S

5 S6, S7, and S8 of the current 3x3 neighbourhood are fed to the D, H and V counters. The D counter counts the number of diagonal coefficients (S1, S8, S3, and S6 that are significant S 20 and generates a 2-bit result 1=1, 2=2, and The H and V counters count the number of horizontal (S 4 and S 5 and vertical (S 2

S

7 coefficients respectively that are significant, and generate a 2-bit result 1=1, 2=2, 3=not used). After the significance •999of the coefficients are counted the outputs of D, V and H counters (and the output of significance comparator if necessary) are combined to form an address to the context look-up table shown in Fig. 7, which provides the correct context. Inside the context look-up table there are several look-up tables for various bands, and a table selector to select the output of the desired table.

564747.doc -16- The context generation logic device 506 generates one of 5 different context states depending on the sign and significance of the immediate vertical and horizontal neighbours of the 3x3 neighbourhood 560 input. The context depends on two variables, h and v, which are determined by the table shown in Fig. 9.

Turning now to Fig. 9, there is illustrated a Table showing the relationship between the two variables h, v and the significance and sign of neighbours A and B during the sign encoding mode. The variable h is a function of the significance of the immediate horizontal neighbours A and B of the current centre position X) of the 3x3 neighbourhood. Similarly, variable v is a function of the significance of the immediate vertical neighbours A and B of the current centre position X) of the 3x3 neighbourhood. The context generation logic device 506 determines these variables h and v by using table as shown in Fig. 9. After determining what h and v are, the context generation logic device 506 then determines what the context is with the help of the table 15 shown in Fig. Turning now to Fig. 10, there is illustrated a Table showing the relationship :°oooe between the variables h, v and the predicted sign x and the context states during the sign encoding mode. The context generation logic device 506 determines the context state and S•the predicted sign X from these variables h, v using the table shown in Fig. Turning now to Fig. 11, there is shown a schematic block diagram of the logic circuitry of the context generation logic device 506 for looking up the context states during the sign coding mode. The sign bits and significance of the vertical and horizontal neighbours are fed into the vertical counters and horizontal counters respectively. Both vertical and horizontal counters implement the above table shown in Fig. 9, and outputs v and h respectively. They are combined to form an address into the context and sign lookup table shown in Fig. 10, which outputs the context required and the predicted sign X.

The predicted sign x is XOR-ed with the original sign bit to produce the data for the arithmetic coder.

564747.doc -17- Fig. 12 illustrates how the list memory 510 can be implemented in the preferred embodiment. The List memory 510 contains the positions of the coefficients in the order in which they should be processed in the significance propagation pass, magnitude refinement pass and cleanup pass.

The List Memory Manager 510 generates and maintains three lists for each bitplane from the maximum significant bitplane to the least significant bitplane. These lists are referred to herein as the Significance Propagation list (SP list); a Magnitude Refinement list (MR list); and a Cleanup list (N list).

Preferably, the list memory 510 has only one entry per coefficient in the block, so the cost is proportional to the size of the block. Each entry in the memory contains the following information: Position of the coefficient, Whether it is significant in this bit plane.

At the top of the memory 510 are the coefficients in the MR list. The size of this portion occupied by these significant coefficients is determined by the size of the MR list.

The cleanup list follows the MR list, and it starts right after the end of the MR list. The oooo SP list starts from the end of the memory, and propagates towards the beginning of the memory. During the SP pass, a number of positions may be required to be transferred to the MR list. However, this will result in these positions being decoded twice for that bitplane. In order to avoid this occurring, these positions are tagged and are transferred to 20 the MR list after the current MR list is processed. The internal organisation causes no wastage in list memory 512.

Turning now to Figs. 6(a) and there is shown a flow chart of a subprocedure 600 for use in the method for entropy decoding symbols in accordance with the preferred embodiment. The method for entropy decoding symbols is preferably implemented in dedicated hardware such as described with reference to Fig. The sub-procedure 600 is called when the method enters the significance propagation decoding phase during the decoding of symbols of a bitplane of the code 564747.doc -18block. The method also comprises sub-procedures for the magnitude refinement decoding phase and cleanup decoding phase.

The method generates and maintains three lists for each bitplane from the most significant bitplane to the least significant bitplane. These lists are a Significance Propagation list (SP list); a Magnitude Refinement list (MR list); and a Cleanup list (N list). These lists contain the positions of the bit symbols within the code block that are to be decoded during the current passes. For instance, the Significance Propagation list contains a list of all those positions of the symbols within the code block that are to be decoded during a current Significance Propagation Pass. The Significance Propagation list is also updated during the current Significance Propagation Pass by the addition and deletions of further positions as needed. In addition, the positions within each of these lists are indexed according to the code block scanning order (see Fig. 2).

The Significance Propagation list (SP list) and Magnitude Refinement list (MR list) i are empty for the highest bitplane that has a non-zero bit and are not called by the method during the decoding(or encoding) of this bitplane. On the other hand, the Cleanup list (N .oo.

list) is assumed to be a list of all the positions within the code block and is called for the decoding of the highest bitplane having a non-zero bit. Initially, the method calls a •cleanup sub-procedure for the cleanup decoding phase of the most significant bitplane.

During this phase, when a decoded symbol is found to be significant, its associated position is deleted from the cleanup list and added to the MR list. After the completion of the first cleanup decoding phase, the method then determines those insignificant neighbours of the positions listed in the MR list. The positions of these insignificant neighbours are then deleted from the cleanup list and added to the SP list. The method then proceeds to the Significance Propagation sub-procedure, the Magnitude Refinement sub-procedure, and the cleanup sub-procedure in that order for each next bitplane. During the SP decoding phase, when a decoded symbol is found to be significant, its associated position is tagged. These tagged positions are then deleted from the SP list and added to MR list after the completion of the next MR decoding phase in order to avoid decoding 564747.doc -19twice. Also during the SP decoding phase, when a decoded symbol is found to be significant, the SP sub-procedure determines the insignificant neighbours of the position of that significant decoded symbol. The SP sub-procedure deletes these insignificant neighbours from the cleanup list and adds these insignificant neighbours to the SP list (if not already on the SP list). The SP sub-procedure then re-indexes the SP list in accordance with the scanning order. The method then proceeds to the MR decoding phase, after which the above mentioned SP tagged positions are added to the MR list and the MR list is re-indexed in accordance with the scanning order. The method then proceeds to a second cleanup pass. During the second cleanup decoding phase, when a decoded symbol is found to be significant, its associated position is deleted from the cleanup list and added to a temporary MR list. After the completion of the second cleanup decoding phase, the method then determines those insignificant neighbours of the positions listed in the temporary MR list. The positions of these insignificant neighbours are then deleted from the cleanup list and added to a temporary SP list. The temporary MR list and temporary SP list are then merged with the existing MR list and SP list ee• respectively. The newly merged MR and SP lists are then re-indexed in accordance with the scanning order. The method then continues to the next bitplane.

•The method during initialisation generates a significance table. This significance table comprises a two-dimensional array of significance states of the coefficients of the 20 code block to be decoded. Initially, each entry of the array is set to zero indicating that each coefficient has an insignificant state. The significance state of a coefficient transitions to one when the coefficient's first non-zero bit-plane value is decoded and the corresponding entry of the array is reset to one The significance propagation subprocedure 600, magnitude refinement sub-procedure, and cleanup sub-procedure all utilise the significance table. The significance table may be updated during any called significance propagation sub-procedure 600 or during any called cleanup sub-procedure.

When the method enters the decoding phase of a new bitplane, it checks whether there are any positions in the current Significance Propagation list and if so the method 564747.doc calls the sub-procedure 600 passing the current bitplane number. If they are no positions in the current Significance Propagation list, the method proceeds to the Magnitude Refinement Pass.

The significance propagation sub-procedure 600 commences at step 602, where any necessary parameters are initialised. In particular, the sub-procedure 600 during commencement 602 generates the context state of the first symbol to be decoded in accordance with the zero coding mode of the draft JPEG 2000 standard.

The significance propagation sub-procedure 600 is in the form of a loop, processing each symbol to be decoded from the bitstream in turn for each pass of the loop. The loop commences at decision block 604 for a symbol to be decoded and returns to decision block 604 after the completion of steps 630, 640, or 642 for the next pass of the loop and the next symbol to be decoded.

After commencement 602, the sub-procedure proceeds to decision block 604, where a check is made whether or not the current context for the current symbol to be decoded 15 was generated in accordance with the sign coding mode. Initially, the current context is a oooo zero coding context generated during commencement 602. In later passes, the current context for the current symbol to be decoded is determined during a previous pass of loop. Generally speaking, the current context is either generated in accordance with a sign coding mode or a zero coding mode during a previous pass of the loop. Specifically, the current context is either: a sign coding context generated during step 614 of a previous pass of the loop and selected during step 642 of the last previous pass of the loop; a zero coding context of the next position in the SP list generated during step 620 of a previous pass of the loop and selected during step 640 of the last previous pass of the loop; or a zero coding context of the next position in the SP list generated during step 630 of a previous pass of the loop; or the zero coding context initialised during commencement 602.

If the decision block 604 returns false that is the current context is a zero coding context, then the sub-procedure 600 proceeds to both steps 606 and 612 and 564747.doc -21performs a first stream of operations (612) and a second stream of operations {(606,618,608,614) and (606,610,616,620)} simultaneously. The second stream of operations comprises a first sub-stream of operations (618,608, and 614) and a second sub-stream of operations (610, 616, and 620) which are also performed simultaneously.

Alternatively, these two sub-streams may be performed sequentially. After the completion of the first stream, the first and second sub-streams, the sub-procedure 600 then proceeds to a single stream of operations 632, 634, 636, 638, 640, 642). It is likely, that the first stream, the first and second sub-streams will not finish their operations at the same time. The sub-procedure 600 includes a further step (not shown) prior to decision block 632, whereby the decision block 632 does not commence its operations until all of these three streams have completed their operations.

During step 606, the sub-procedure 600 retrieves the first position in the indexed Significance Propagation list, which has not been previously retrieved, as the current S" position. After completion of step 606, the sub-procedure 600 proceeds to both steps 618 and 610.

The sub-procedure 600 during step 612, decodes the current symbol received from the bitstream. The decoding step 612 requires as input the symbol to be decoded and the current context state of that symbol. The current context is the zero coding context generated during a previous pass of the loop or if it is the first pass of the loop the zero 20 coding context generated during commencement of the sub-procedure 600. Once decoded, the bit symbol's location within the code block is specified by the current position obtained in step 606 and the current bitplane number. The decoded bit is then output (not shown) for reconstituting the transform coefficients of the code block. After the decoding step 612, the sub-procedure proceeds to decision block 632.

The sub-procedure 600 during decision block 618, checks whether or not the current significance states of the 3x3 neighbourhood of the current position have already been fetched from memory. The current position in the significance propagation list may not have changed from the last loop of the sub-procedure 600. This can occur when the 564747.doc -22- 3x3 neighbourhood is retrieved during step 630 of a previous loop. If the current position has not changed from the last loop, then the sub-procedure 600 does not need to fetch the information again. If this occurs, the sub-procedure proceeds directly to step 614, otherwise it proceeds to step 608.

During step 608, the current significance states of the coefficients of a 3x3 neighbourhood of the current position are fetched from memory. The current position is that position fetched in step 606 and is the position within the code block of the symbol presently being decoded in step 612. For example, the significance states of a 3x3 neighbourhood of a coefficient X[m,n] is illustrated in Fig. 1, where m is the row and n the column of the code block. After completion of step 608, the sub-procedure then proceeds to step 614.

The sub-procedure 600 then generates 614 the context state in accordance with the sign coding mode described in the draft JPEG 2000 standard and based on the 3x3 neighbourhood of the current position obtained during step 608 or previously fetched.

After completion of this step 614, the sub-procedure 600 proceeds to decision block 632.

During step 610, the sub-procedure 600 determines the next position after the current position of the symbol to be decoded in the indexed Significance Propagation list.

If there is no next position 616 in the indexed Significance Propagation list, namely the current position is the last position in the list, the sub-procedure 600 proceeds directly to S 20 decision block 632. If there is another position 616 in the indexed Significance Propagation list after the current position then the sub-procedure 600 proceeds to step 620.

During step 620, the sub-procedure 600 selects the current significance states of the coefficients in the 3x3 neighbourhood surrounding the next position in the Significance list, and generates a context state based upon these significance states. This context state is generated in accordance with zero coding mode described in the draft JPEG 2000 standard mentioned above. After completion of step 620, the sub-procedure 600 proceeds to decision block 632.

564747.doc The sub-procedure 600 commences operation of the decision block 632, once the contexts have been generated 614 and 620 and the current symbol has been decoded 612.

The decision block 632 makes a check whether or not the current decoded bit is significant, namely whether or not the decoded bit is one If the current decoded bit is not significant, then the sub-procedure 600 proceeds to decision block 636, where a check is made whether or not there is no next position in the Significance Propagation list. That is, the decision block 636 checks whether all the positions within the Significance Propagation Pass list have been previously retrieved and processed. If there are still positions within the Significance Propagation list to be retrieved and processed, the subprocedure 600 then proceeds to step 640. If there are no positions within the Significance Propagation list, the sub-procedure 600 terminates 638 and returns to the calling method.

The sub-procedure 600 during step 640 selects the context generated during step 620 as the current context. Namely, it selects the zero coding context of the next position in the significance propagation list as the current context. This current context is then used in the decoding 612 of the next symbol to be decoded during the next pass of S.the loop.

If on the other hand, the decision block 632 determines that the current decoded bit is significant, then the sub-procedure 600 proceeds to steps 634 and 642. The subprocedure 600 then updates 634 the significance propagation list. Specifically, the SP 20 sub-procedure determines the insignificant neighbours of the current position of the decoded symbol. The SP sub-procedure then deletes these insignificant neighbours from the cleanup list and adds these insignificant neighbours to the SP list (if not already on the SP list). The SP sub-procedure then re-indexes the SP list in accordance with the scanning order.

Simultaneously with step 634, the sub-procedure proceeds to step 642, where the sub-procedure 600 selects the context generated during step 614 as the current context.

Namely, it selects the sign coding context of the current position as the current context.

564747.doc -24- This current context is then used in the decoding 624 of the next symbol to be decoded during the next pass of the loop.

After the completion of steps 642 or 640, the sub-procedure 604 returns to decision block 604 for the processing of the next symbol to be decoded.

If on the other hand, the decision block 604 returns true (Yes), that is the current context is a sign coding context, then the sub-procedure 600 proceeds to both steps 622 and 624 and performs a first stream of operations (624) and a second stream of operations (622, 626, 628, 630) simultaneously. After the completion of the first and second streams, the sub-procedure 600 then returns to decision block 604 for the processing of the next symbol to be decoded. It is likely, that the first and second streams will not finish their operations at the same time. The sub-procedure 600 includes a further step (not shown) after steps 630 and 624 and prior to decision block 604, whereby the decision block 604 does not commence its operations until both of these two streams have completed their operations.

The sub-procedure 600 during step 624, decodes the current symbol received from the bitstream. The decoding step 624 requires as input the symbol to be decoded and the °9.

•current context state of that symbol. The current context is the sign coding context generated during step 614 of the previous pass of the loop. Once decoded, the bit symbol's location within the code block is specified by the position obtained in step 606 of the last previous pass of the loop. The decoded bit is then output (not shown) for reconstituting the transform coefficients of the code block. After the decoding step 624, the sub-procedure returns to decision block 604 for the processing of the next symbol to be decoded.

During step 622, the sub-procedure 600 determines the next position after the current position of the symbol to be decoded in the indexed Significance Propagation list.

O If there is no next position 626 in the indexed Significance Propagation list, namely the current position is the last position in the list, the sub-procedure 600 terminates and returns to the calling method. If there is another position 616 in the indexed Significance 564747.doc Propagation list after the current position then the sub-procedure 600 proceeds to decision block 628.

In decision block 628, a check is made whether the current significance states of the 3x3 neighbourhood of this next position have already been fetched from memory and a context state generated. The next position in the Significance Propagation list may not have changed from the last loop of the sub-procedure 600. If the next position has not changed from the last loop, then the sub-procedure 600 does not need to fetch the information and generate the context state again. If this occurs, the sub-procedure 600 proceeds directly to decision block 604, otherwise it proceeds to step 630.

During step 630, the sub-procedure 600 fetches the current significance states of the coefficients surrounding the next position in the Significance list, and generates a context state based upon these significance states. This context state is generated in accordance with zero coding mode described in the draft JPEG 2000 standard mentioned above. The i* :sub-procedure selects this context as the current context. This current context is then used 15 in the decoding 612 of the next symbol to be decoded during the next pass of the loop.

After completion of step 630, the sub-procedure 600 returns to decision block 604 for processing of the next symbol to be decoded.

As can be seen, the sub-procedure 600 simultaneously decodes the current symbol to be decoded (612 or 624), and generates the context for the symbol to be decoded during the next pass of the loop (614, 620, or 630) thus maximising the throughput.

The aforementioned preferred sub-procedure comprises a particular control flow.

There are many other variants of the preferred sub-procedure, which use different control flows without departing the spirit or scope of the invention.

The sub-procedure 600 may also be modified for use during the cleanup pass. The clean up sub-procedure would be substantially the same as the significance propagation sub-procedure, however it would use the cleanup list instead of the SP list and the updating step 634 would be omitted.

Industrial Applicability 564747.doc -26- It is apparent from the above that the embodiment(s) of the invention are applicable to the computer and video graphics industries and related fields such as video and camera industries).

The foregoing describes only some embodiments of the present invention, and modifications and/or changes can be made thereto without departing from the scope and spirit of the invention, the embodiment(s) being illustrative and not restrictive.

In the context of this specification, the word "comprising" means "including principally but not necessarily solely" or "having" or "including" and not "consisting only of'. Variations of the word comprising, such as "comprise" and "comprises" have corresponding meanings.

e 564747.doc

Claims (5)

1. A method for entropy decoding symbols, the method simultaneously performing a first set of one or more steps and a second set of one or more steps, wherein said first set comprises the step of: entropy decoding a current symbol to be decoded using said current symbol to be decoded and a current context; and said second set comprises the steps of: determining a first context; determining a second context; and selecting one of the determined contexts as the next current context based on the current decoded symbol; ".repeating the first and second sets of steps for the next symbols to be decoded in turn. Is

2. A method as claimed in claim 1, wherein the selecting step comprises selecting one of the first or second context based on a significance state of the current decoded symbol.

3. A method as claimed in claim 1, wherein the method comprises the step of generating and maintaining a list of positions within a code block of said symbols that are 20 to be decoded.

4. A method as claimed in claim 3, wherein the method .comprises the step of retrieving the first position in said list, which has not been previously retrieved, as the current position of the symbol to be decoded. A method as claimed in claim 4, wherein the second context is generated in accordance with a second predetermined mode of operation and is based on the

564747.doc -28 significance states of the surrounding neighbours of the current position of the symbol to be decoded. 6. A method as claimed in claim 4, wherein the first context is generated in accordance with a first predetermined mode of operation and is based on the significance states of the surrounding neighbours of the next position in the list after the current position in a predetermined scanning order. 7. The method as claimed 4, wherein the method comprises the steps of: updating, if the current decoded symbol is significant, the list to include the positions of any insignificant neighbours of the current decoded symbol after the current position in a predetermined scanning order which are not already on the list; and ~re-indexing said positions of the updated list in accordance with a predetermined scanning order. a...o A method as claimed in claim 1, wherein said decoded symbols constitute a code block of transform coefficients. 9. A method for entropy decoding symbols, the method simultaneously performing a 20 first set of one or more steps and a second set of one or more steps if a current context was generated in accordance with a first predetermined mode of operation and the method i ••simultaneously performing a third set of one or more steps and fourth set of one or more steps if the current context was generated in accordance with a second predetermined mode of operation, wherein said first set comprises the step of: entropy decoding a current symbol to be decoded using said current symbol to be decoded and the current context, wherein said current context was previously generated in accordance with said first predetermined mode of operation; and said second set comprises the steps of: 564747.doc -29- determining a first context in accordance with said first predetermined mode of operation; determining a second context in accordance with said second predetermined mode of operation; and selecting one of the generated contexts as the next current context based on the current decoded symbol; and said third set comprises the step of: entropy decoding a current symbol to be decoded using said current symbol to be decoded and the current context, wherein said current context was previously generated in accordance with the second predetermined mode of operation; and said fourth set comprises the steps of: determining a third context in accordance with the first predetermined mode of operation; and selecting the third context as the next current context based on the current decoded 15 symbol; and ooo9 repeating the first and second sets of steps or the third and fourth sets of steps for the next symbols to be decoded in turn. oooo A method as claimed in claim 9, wherein the step of selecting one of the generated contexts comprises selecting one of the first or second contexts based on a significance state of the current decoded symbol. 11. A method as claimed in claim 9, wherein the method comprises the step of generating and maintaining a list of positions within a code block of said symbols that are to be decoded. 564747.doc 12. A method as claimed in claim 11, wherein the method comprises the step of retrieving the first position in the list, which has not been previously retrieved, as the current position of the symbol to be decoded. 13. A method as claimed in claim 12, wherein the second context is based on the significance states of the surrounding neighbours of the current position of the symbol to be decoded. 14. A method as claimed in claim 12, wherein the first context is based on the significance states of the surrounding neighbours of the next position in the list after the current position in a predetermined scanning order. 15. The method as claimed 12, wherein the method comprises the steps of: o updating, if the current decoded symbol is significant, the list to include the positions of any insignificant neighbours of the current decoded symbol after the current position in a predetermined scanning order which are not already on the list; and re-indexing said positions of the updated list in accordance with a predetermined scanning order. 20 16. A method as claimed in claim 9, wherein said decoded symbols constitute a code block of transform coefficients. too to *.to 17. Apparatus for entropy decoding symbols, the apparatus comprising: an entropy decoder for entropy decoding a current symbol to be decoded having as input said current symbol to be decoded and a current context; a context generator for generating a first context in accordance with a first predetermined mode of operation; 564747.doc -31- a context generator for generating a second context in accordance with a second predetermined mode of operation; and a selector for selecting one of the generated contexts as the next current context of the next symbol to be decoded based on the current decoded symbol. 18. Apparatus as claimed in claim 17, wherein the selector selects one of the generated contexts based on a significance state of the current decoded symbol. 19. Apparatus as claimed in claim 17, wherein the apparatus comprises a memory manager for generating and maintaining in memory a list of positions within a code block of said symbols that are to be decoded. Apparatus as claimed in claim 19, wherein the apparatus comprises means for retrieving the first position in the list, which has not been previously retrieved, as the current position of the symbol to be decoded. :21. Apparatus as claimed in claim 20, wherein the second context is based on the **significance states of the surrounding neighbours of the current position of the symbol to be decoded. S 22. Apparatus as claimed in claim 20, wherein the first context is based on the significance states of the surrounding neighbours of the next position in the list after the current position in a predetermined scanning order. V0 0 25 23. Apparatus as claimed 20, wherein the apparatus comprises: means for updating, if the current decoded symbol is significant, the list to include o: the positions of any insignificant neighbours of the current decoded symbol after the current position in a predetermined scanning order which are not already on the list; and 564747.doc -32 means for re-indexing said positions of the updated list in accordance with a predetermined scanning order. 24. Apparatus as claimed in claim 17, wherein said decoded symbols constitute a code block of transform coefficients. Apparatus as claimed in claim 17, wherein said apparatus operates in a first mode of operation if the previous decoded symbol was found to be insignificant and in a second mode of operation if the previously decoded symbol was found to be significant, and said apparatus during the first mode of operation generates the first and second contexts in accordance with the first and second predetermined modes of operation respectively and selects one of the generated contexts based on the current decoded symbol and said apparatus during the second mode of operation generates the first context in accordance with the first predetermined mode of operation and selects the generated first context. 26. A method substantially as described herein with reference to any one of the •embodiments as illustrated in Figs.

5 to 12. 27. Apparatus substantially as described herein with reference to any one of the embodiments as that embodiment is illustrated in Figs. 5 to 12. DATED this fifth Day of March, 2003 CANON KABUSHIKI KAISHA Patent Attorneys for the Applicant SPRUSON FERGUSON 564747.doc