AN2121 Freescale Semiconductor / Motorola, AN2121 Datasheet
AN2121
Available stocks
Related parts for AN2121
AN2121 Summary of contents
Page 1
... Freescale Semiconductor, Inc. JPEG2000 Arithmetic Encoding on the StarCore SC140 For More Information On This Product, Go to: www.freescale.com Application Note by Sue Twelves and Mike Wu AN2121/D Rev 1.0, 10/2001 ...
Page 2
Freescale Semiconductor, Inc. Motorola reserves the right to make changes without further notice to any products herein. Motorola makes no warranty, representation or guarantee regarding the suitability of its products for any particular purpose, nor does Motorola assume any liability ...
Page 3
Freescale Semiconductor, Inc. Abstract and Contents This application note describes how the advanced features of the StarCore processor can be used to implement the arithmetic coding algorithm employed in the JPEG2000 image compression standard. Both C code and optimized assembler ...
Page 4
Freescale Semiconductor, Inc. 3.2.3 If-Then-Else Decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...
Page 5
Freescale Semiconductor, Inc. 1 Introduction This application note is the second in a series of notes that describe how the advanced features of the StarCore processor can be used to implement the algorithms associated with the image compression standard JPEG2000. ...
Page 6
Freescale Semiconductor, Inc. Background Theory 2 Background Theory This section presents a look at some of the theory behind symbol coding, including the well-known Huffman coder, general arithmetic coding, and binary arithmetic coding, which is employed by the JPEG2000 standard. ...
Page 7
Freescale Semiconductor, Inc. • Iterate the first two steps until the symbols are arranged in a binary tree in which only two branches extend from each root. • Assign ‘1’ to one branch from each root, and ‘0’ to the ...
Page 8
Freescale Semiconductor, Inc. Background Theory 2.1.2 Limitations of Huffman Coding In the above example, the code rate and the entropy are the same value, 1.75, because the probability for – l each symbol is equal to 2 where, as before, ...
Page 9
Freescale Semiconductor, Inc. Whereas Huffman coding involves transmitting separate code words for each symbol in a sequence, arithmetic coding requires transmitting only the information needed to allow a decoder to determine the particular fractional interval between 0 and 1 to ...
Page 10
Freescale Semiconductor, Inc. Background Theory proportional to the probability associated with each symbol. For example, the symbol interval of width 1/2 at position [3/8, 7/8).Note that for arithmetic coding the ordering of the intervals is arbitrary, whereas in Huffman coding ...
Page 11
Freescale Semiconductor, Inc. In binary fraction format 0.01 + 0.001 = 0.011 1 3. Update the interval, A, using the equation For the first symbol in the example binary fraction format ...
Page 12
Freescale Semiconductor, Inc. Background Theory 512 In binary fraction format 0.1011001 0.000001 0.01 = 0.00000001 4 Therefore, ...
Page 13
Freescale Semiconductor, Inc 0.01 0. 0.01 0.0111 0.0011 F (occurs 0. 0.010011 0.000011 F ...
Page 14
Freescale Semiconductor, Inc. Background Theory Encoding the first symbol Given [0, 1) with subintervals [C, C+( [0, 0.01) e ‘T’ occurs 0.01 1 ...
Page 15
Freescale Semiconductor, Inc. Subinterval [0.01, 0.0111) becomes the new interval Decoding the third symbol Given: interval [0.01, 0.0111) with subintervals [0.01, 0.010011) and [0.010011, 0.0111) Since C = 0.010011 lies within [0.010011, 0.0111), the third symbol must be ‘T’. Subinterval ...
Page 16
Freescale Semiconductor, Inc. Background Theory 2.4.1 Removing Multiplication The JPEG 2000 BAC maintains the interval A in the range [0.75, 1. process of renormalization (see Section 2.4.4). This means that the interval is always approximately equal to 1, ...
Page 17
Freescale Semiconductor, Inc. 2.4.2.2 MPS Case If an MPS (‘0’ for context CX) is received, the CODEMPS procedure (see Figure C-7 on page 42) is called. When symbol ‘0’ (MPS for CX) occurs, normally the length of the interval A ...
Page 18
Freescale Semiconductor, Inc. Background Theory Table 2. A Portion Table C-2 From the JPEG2000 FDIS Index Hexadecimal 29 $1101 0001 0001 0000 0001 30 $0AC1 0000 1010 1100 0001 31 $09C1 0000 1001 1100 0001 32 $08A1 0000 1000 1010 ...
Page 19
Freescale Semiconductor, Inc. By buffering the completed bytes from the C register, the B register always keeps a byte just removed from the C register before the byte is sent to the output code stream. A shift counter, CT, counts ...
Page 20
Freescale Semiconductor, Inc. Background Theory The decoder checks the bit following any $FF byte. If the bit is set, the decoder knows that a carry has occurred. 2.4.6 Software Versus Custom Hardware Implementation In the binary arithmetic coding scheme described ...
Page 21
Freescale Semiconductor, Inc. 3 Implementation This section describes the software written for a StarCore implementation of the JPEG2000 arithmetic coder. Appendix listing of the C code, and Appendix B lists the assembly code. All variables in the ...
Page 22
Freescale Semiconductor, Inc. Implementation 3.1.1 Encoder Initialization The encoder initialization is illustrated in Figure C-10 on page 47. The coder is initialized to the following conditions: • The interval length is set $8000, equivalent to 0.75 in ...
Page 23
Freescale Semiconductor, Inc. The marker code has a prefix of $FF which can be made to overlap the final bits of the compressed data by ensuring that the final bits of the C register are also $FF. This means that ...
Page 24
Freescale Semiconductor, Inc. Implementation Table 3. Processing Time for C Version of Arithmetic Encoder Typical image Constant grey scale For comparison, the arithmetic coder was tested on Motorola’s DSP56307 with the constant grey scale image, where it was calculated that ...
Page 25
Freescale Semiconductor, Inc. 3.2.1.2 Multiple Address Registers The context table is split into two separate look-up tables in Appendix B—one for the indices and one for the MPS associated with each context— to highlight the advantage of StarCore's numerous address ...
Page 26
Freescale Semiconductor, Inc. Implementation Code Example 6. T Bit Selects an Instruction tfrt d7,d0 In Code Example 6, if the T bit is set transferred to d0; otherwise d7 is added to d1. 3.2.4 Results Table 4 compares ...
Page 27
Freescale Semiconductor, Inc. 4 Summary The arithmetic encoder C code given in Appendix A takes 4.6M cycles to complete one typical 128 pixel grey scale image, which corresponds to a processing time of 2 seconds to complete a color 1 ...
Page 28
Freescale Semiconductor, Inc. References 5 References [1] S. Twelves, A. White, M. Wu, JPEG2000 Wavelet Transform Using StarCore, Motorola application note, order number AN2089/D. [2] C. Shannon, A Mathematical Theory of Communication, Bell System Technical Journal, Vol. 27, pp. 379–423, ...
Page 29
Freescale Semiconductor, Inc. Appendix A Arithmetic Encoder: C Code Arithenc implementation of the MQ arithmetic encoder described in Annex C of the JPEG2000 FDIS,[4]. All data types converted to uint32. Context variables made global, rather than access via ...
Page 30
Freescale Semiconductor, Inc. /* ======================================================================== */ /* Define these inputs to have different data types */ static uint32 Qe[47 0x5601UL, 0x3401UL, 0x1801UL, 0x0ac1UL, 0x0521UL, 0x0221UL, 0x5601UL, 0x5401UL, 0x4801UL, 0x3801UL, 0x3001UL, 0x2401UL, 0x1c01UL, 0x1601UL, 0x5601UL, 0x5401UL, 0x5101UL, 0x4801UL, 0x3801UL, ...
Page 31
Freescale Semiconductor, Inc. for ( <= MAXCONTEXT; i++) { contexts[i]. contexts[i].MPS = 0; } contexts[UNIFORM_CX].I = 46; contexts[RUNLENGTH_CX]. contexts[0]. ArithEncInit */ /* ======================================================================== */ /* Perform the bottom right ...
Page 32
Freescale Semiconductor, Inc. ByteOutRight(); } } } else ByteOutRight(); } /* ByteOut */ /* ======================================================================== */ /* Renormalize the lower bound and size of the probability range. See Section C.2.6 and Figure C- least 0.75 */ static inline ...
Page 33
Freescale Semiconductor, Inc >= QeI) else I = NMPS[I]; Renorme(); } /**/ } else { /* CodeLPS */ A -= QeI; /* Doing this test first might speed up process */ if (A >= QeI QeI; ...
Page 34
Freescale Semiconductor, Inc. Encoder test harness for the MQ arithmetic encoder described in Annex C of JPEG2000. This main program performs arithmetic encoding, given context-bit pairs stored in arrayIn[]. author Matthew Leditschke version $Revision: 1 #include ...
Page 35
Freescale Semiconductor, Inc. #include <stdlib.h> #include "types.h" #include "fileIO.h" /* Store the encoded bytes for testing */ extern uint8 arrayOut[]; /* Keep track of the total number of bytes written */ static uint32 bytesWritten = 0; /* This writes out ...
Page 36
Freescale Semiconductor, Inc. if (feof(inFile)) byte |= 0x01; } #endif #ifdef WRITE_BYTES byte = getc(inFile); if (feof(inFile)) byte = 0xFF; #endif #ifdef NO_WRITE fprintf(stderr, "Nothing was written, so there is nothing to read.\n"); exit(EXIT_FAILURE); #endif return byte TransmitByte ...
Page 37
Freescale Semiconductor, Inc unsigned 32 bit integer */ typedef unsigned long int uint32 unsigned 24 bit integer */ typedef unsigned long int uint24 unsigned 16 bit integer */ typedef unsigned short int uint16; /* ...
Page 38
Freescale Semiconductor, Inc. 34 JPEG2000 Arithmetic Encoding on the StarCore SC140 For More Information On This Product, Go to: www.freescale.com ...
Page 39
Freescale Semiconductor, Inc. Appendix B Arithmetic Encoder: Assembly Code ;********************************************************************************* ; Arithmetic Encoder - Assembly Code ;********************************************************************************* ; FILENAME : arith_enc.asm ; PREPARED BY : MOTOROLA Australia Research Centre, 8 January 2001 ; AUTHOR : Sue Twelves ;********************************************************************************* ; ALGORITHM ...
Page 40
Freescale Semiconductor, Inc. dcw $4801,$0048,$0070,$0000,$3801,$0050,$0070,$0000 dcw $3001,$0058,$0088,$0000,$2401,$0060,$0090,$0000 dcw $1c01,$0068,$00a0,$0000,$1601,$00e8,$00a8,$0000 dcw $5601,$0078,$0070,$0001,$5401,$0080,$0070,$0000 dcw $5101,$0088,$0078,$0000,$4801,$0090,$0080,$0000 dcw $3801,$0098,$0088,$0000,$3401,$00a0,$0090,$0000 dcw $3001,$00a8,$0098,$0000,$2801,$00b0,$0098,$0000 dcw $2401,$00b8,$00a0,$0000,$2201,$00c0,$00a8,$0000 dcw $1c01,$00c8,$00b0,$0000,$1801,$00d0,$00b8,$0000 dcw $1601,$00d8,$00c0,$0000,$1401,$00e0,$00c8,$0000 dcw $1201,$00e8,$00d0,$0000,$1101,$00f0,$00d8,$0000 dcw $0ac1,$00f8,$00e0,$0000,$09c1,$0100,$00e8,$0000 dcw $08a1,$0108,$00f0,$0000,$0521,$0110,$00f8,$0000 dcw $0441,$0118,$0100,$0000,$02a1,$0120,$0108,$0000 dcw $0221,$0128,$0110,$0000,$0141,$0130,$0118,$0000 dcw $0111,$0138,$0120,$0000,$0085,$0140,$0128,$0000 dcw $0049,$0148,$0130,$0000,$0025,$0150,$0138,$0000 dcw $0015,$0158,$0140,$0000,$0009,$0160,$0148,$0000 dcw ...
Page 41
Freescale Semiconductor, Inc. dcb $07,$01,$10,$00,$03,$01,$0d,$00,$03,$01,$0d,$00,$03,$01,$0d,$00 dcb $03,$01,$0d,$00,$07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00 dcb $07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00 dcb $07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00 dcb $07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00 dcb $07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00 dcb $07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00 dcb $07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00 dcb $07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00 dcb $07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00 dcb $07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00 dcb $07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00 dcb $07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00 dcb $07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00 dcb $07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00 dcb $07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00,$07,$01,$10,$00 dcb $07,$01,$10,$00,$06,$01,$0f,$00,$07,$01,$10,$00,$07,$01,$10,$00 dcb $07,$01,$10,$00,$06,$01,$0f,$00,$07,$01,$10,$00,$07,$01,$10,$00 dcb ...
Page 42
Freescale Semiconductor, Inc. ; Need CX-1 because context table:MPS starts Initialize the arithmetic encoder - Fig C-10 INITENC: moveu.w #RENORM_THRESH,d0 BPST-1 ; output compressed bitstream (BP in FDIS) ; This is BPST-1, i.e. the ...
Page 43
Freescale Semiconductor, Inc > 0.75 no renormalisation is required. i.e. A and 0x8000 not = < 0.75, needs renormalisation ; the most sigfig number is not set ; therefore, A has fallen below ...
Page 44
Freescale Semiconductor, Inc. jfd nobitstuffyet bitstuff: tfr d1,d11 asrr #20,d11 and #$ffff,d1.l jmpd endbyteout move.w #7,d4 and #$000f,d1.h nobitstuffyet: cmpgt d1,d10 jt outputbyte inc d2 bmtsts #$ff,d2.l jf outputbyte and #$ffff,d1.l jmpd bitstuff and #$07ff,d1.h outputbyte: tfr d1,d11 asrr #19,d11 ...
Page 45
Freescale Semiconductor, Inc. Appendix C Excerpts from FDIS This appendix reproduces several flow diagrams and a table from Appendix ISO/IEC FDIS 15444-1 : 2000 ( Figure C-1. Arithmetic Encoder Inputs and Outputs Figure C-2. Encoder ...
Page 46
Freescale Semiconductor, Inc. FLUSH CODELPS CODELPS 42 JPEG2000 Arithmetic Encoding on the StarCore SC140 For More Information On This Product, ENCODE Yes Done Figure C-3. ENCODE Procedure CODE1 Yes No MPS(CX Done Figure C-4. ...
Page 47
Freescale Semiconductor, Inc. CODELPS – Qe(I(CX < Qe(I(CX))? (I(CX)) e Yes SWITCH(I(CX)) MPS(CX – MPS(CX) I(CX) = NLPS(I(CX)) RENORME Figure C-6. CODELPS Procedure with Conditional MPS/LPS Exchange Appendix C. Excerpts ...
Page 48
Freescale Semiconductor, Inc. CODEMPS – Qe(I(CX AND $8000 = (I(CX I(CX) = NMPS(I(CX)) RENORME Figure C-7. CODEMPS Procedure with Conditional MPS/LPS Exchange 44 ...
Page 49
Freescale Semiconductor, Inc. RENORME << << – Yes BYTEOUT A AND $8000 = 0? No Done Figure C-8. Encoder Renormalization Procedure Appendix C. Excerpts ...
Page 50
Freescale Semiconductor, Inc >> AND $7FFFFFF Figure C-9. Encoder BYTEOUT Procedure 46 JPEG2000 Arithmetic Encoding on the StarCore SC140 For More Information On This Product, ...
Page 51
Freescale Semiconductor, Inc. INITENC A = $8000 BPST – $FF? Yes Done Figure C-10. Encoder Initialization Appendix C. Excerpts from FDIS For More Information On ...
Page 52
Freescale Semiconductor, Inc. BYTEOUT BYTEOUT 48 JPEG2000 Arithmetic Encoding on the StarCore SC140 For More Information On This Product, FLUSH SETBITS << << CT Yes B = $FF ...
Page 53
Freescale Semiconductor, Inc. SETBITS TEMPC = $FFFF No C TEMPC? Yes – $8000 Done Figure C-12. Setting the Final Bits in the C Register Appendix C. Excerpts from FDIS For ...
Page 54
Freescale Semiconductor, Inc. Table C-2. Q Index Hexadecimal 0 0x5601 0101 0110 0000 0001 1 0x3401 0011 0100 0000 0001 2 0x1801 0001 1000 0000 0001 3 0x0AC1 0000 1010 1100 0001 4 0x0521 0000 0101 0010 0001 5 0x0221 ...
Page 55
Freescale Semiconductor, Inc. Table C-2. Q Values and Probability Estimation (Continued Index Hexadecimal 28 0x1201 0001 0010 0000 0001 29 0x1101 0001 0001 0000 0001 30 0x0AC1 0000 1010 1100 0001 31 0x09C1 0000 1001 1100 0001 ...
Page 56
Freescale Semiconductor, Inc. 52 JPEG2000 Arithmetic Encoding on the StarCore SC140 For More Information On This Product, Go to: www.freescale.com ...