this might be trivial but I have a brainfog here! I am working through a JPEG compression problem using Huffman codes. According to our book, the process for coding a quantized matrix for a jpeg has three ingredients; the huffman tree for the DC components, another huffman tree for the AC components and an integer identifier table. The problem is to encode the given matrix into bit streams using huffman coding:-
\begin{matrix} -19 & 7 & 2 & -1 & 0 & 0 & 0 & 0 \\ -10 & -5 & 1 & 1 & 0 & 0 & 0 & 0\\ 2 & -1 & -1 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \end{matrix}
This is the given integer identifier table:-
$$ \begin{array}{c} \text{L} & \text{Entry} & \text{Binary}\\ 0 & 0 & -- \\ 1 & -1,1 & 0,1 \\ 2 & -2,-3,3,2 & 00,01,10,11 \\ 3 & -7,-6,-5,-4,4,5,6,7 & 000,001,010,011,100,101,110,111 \\ 4 & -15,-14,...,-8,8,...,14,15 & 0000,0001,...,0111,1000,...,1110,1111 \\ 5 & -31,-30,...,-16,16,...,30,31 & 00000,00001,...,01111,10000,...,11110,11111 \\ 6 & -63,-62,...,-32,32,...,62,63 & 0000000,000001,...,011111,100000,...,111110,111111 \\ . & . & . \\ . & . & . \\ \end{array} $$
Thus far I am clear on determining the size of y for a given 8 * 8 matrix where $Y_0 = -19$ which is 5 and thus translates into 110 using the DPCM tree, however, I can't see the pattern in building the above table for the extra digits for -19. Appreciate any guidance....
It’s not clear to me exactly what you’re asking, so I’ll address the three possibilities that occur to me. Bear in mind, however, that I’ve never worked with the algorithm, and this answer is based entirely on what I’ve picked up by reading in the last couple of hours; you may be working with a slightly different presentation of it.
The integer identification table is constructed in a straightforward manner. If $n$ is a positive integer, we assign to it its ordinary binary representation, which of course has a leading $1$. Thus, for example, $19$ is assigned the string $10011$. If $n$ is a negative integer such that $2^k\le-n<2^{k+1}$, let $f(n)=n+2^{k+1}-1$, and assign to $n$ the ordinary binary representation of $f(n)$ with a leading $\mathbf 0$. For example, $2^4\le 19<2^5$, so $$f(-19)=-19+2^5-1=12\;,$$ and $-19$ is assigned the string $01100$.
To use the integer identification table to construct the intermediate code, process the entries in the $8\times 8$ matrix in zig-zag order. Your first value is $-19$, which is represented by $01100$, a string of length $5$. It is preceded by $0$ zeroes, so the first two elements of the intermediate code are $(0,5),01100$: $0$ zeroes, followed by a $5$-bit code, which is $01100$.
The next entry in the matrix in zig-zag order is $7$, which is encoded as $111$; it is preceded by $0$ zeroes, so the next two elements of the intermediate code are $(0,3),111$: $0$ zeroes, followed by a $3$-bit code, which is $111$.
The next few entries in zig-zag order are $-10,2,-5,2,-1,1,-1,1,0,0,-1,1,0$, and then $64-15=49$ zeroes. The intermediate code is therefore
$$\begin{align*} &\{(0,5),01100,(0,3)111,(0,4),0101,(0,2),10,(0,3),010,(0,2),10,\\ &\;\,(0,1),0,(0,1),1,(0,1),0,(0,1),1,(\color{red}{2},1),0,(0,1),1,(0,0)\} \end{align*}\;.\tag{1}$$
The red $2$ represents the two zeroes before the last $-1$, and the final $(0,0)$ pair indicates that there are no more non-zero entries.
The last step is to use a Huffman encoding to transform $(1)$ into a bit string. The elements to be assigned Huffman codes are the ordered pairs, not counting the final $(0,0)$. Use the following frequency table to construct a Huffman code in the usual way. $$\begin{array}{cc}\text{pair}&\text{frequency}\\ \hline(0,1)&5\\(0,2)&2\\(0,3)&2\\(0,4)&1\\(0,5)&1\\(2,1)&1\end{array}$$ One possible encoding is: $$\begin{array}{cc}\text{pair}&\text{code}\\ \hline (0,1)&0\\(0,2)&110\\(0,3)&111\\(0,4)&100\\(0,5)&1010\\(2,1)&1011\end{array}$$ Now just replace each pair in $(1)$ by its code and leave the bit strings in $(1)$ as they are; the resulting bit string begins $\color{red}{1010}01100\color{red}{111}111\ldots$, where the red bits are the Huffman codes of the first two pairs.