Databases Reference
In-Depth Information
is significant and positive, so we send a 1 followed by a 0. The same is true for the second
offspring, which has a value of 10. So we send another 1 followed by a 0. We move the
coordinates of these two to the LSP. The next two offsprings are both insignificant at this level;
therefore, we move these to the LIP and transmit a 0 for each. As
L
(
,
)
={}
0
1
, we remove
(
,
)
D
from the LIS. Looking at the other elements of the LIS, we can clearly see that both of
these are insignificant at this level; therefore, we send a 0 for each. In the refinement pass we
examine the contents of the LSP from the previous pass. There is only one element in there
that is not from the current sorting pass, and it has a value of 26. The third MSB of 26 is 1;
therefore, we transmit a 1 and complete this pass. In the second pass we have transmitted 13
bits: 0001101000001. The condition of the lists at the end of the second pass is as follows:
0
1
LIP
:{
(
0
,
1
)
→
6
,(
1
,
0
)
→−
7
,(
1
,
1
)
→
7
,(
1
,
2
)
→
6
,(
1
,
3
)
→
4
}
LIS
:{
(
1
,
0
)
D
,(
1
,
1
)
D}
LSP
:{
(
0
,
0
)
→
26
,(
0
,
2
)
→
13
,(
0
,
3
)
→
10
}
=
Third Pass
The third pass proceeds with
n
2. As the threshold is now smaller, there
are significantly more coefficients that are deemed significant, and we end up sending 26
bits. You can easily verify for yourself that the transmitted bitstream for the third pass is
10111010101101100110000010. The condition of the lists at the end of the third pass is as
follows:
LIP
:
{
(
3
,
0
)
→
2
,(
3
,
1
)
→−
2
,(
2
,
3
)
→−
3
,(
3
,
2
)
→−
2
,(
3
,
3
)
→
0
}
LIS
:
{}
LSP
:
{
(
0
,
0
)
→
26
,(
0
,
2
)
→
13
,(
0
,
3
)
→
10
,(
0
,
1
)
→
6
,(
1
,
0
)
→−
7
,(
1
,
1
)
→
7
,
(
1
,
2
)
→
6
,(
1
,
3
)
→
4
,(
2
,
0
)
→
4
,(
2
,
1
)
→−
4
,(
2
,
2
)
→
4
}
Now for decoding this sequence. At the decoder we also start out with the same lists as
the encoder:
LIP
:{
(
0
,
0
), (
0
,
1
), (
1
,
0
), (
1
,
1
)
}
LIS
:{
(
0
,
1
)
D
,(
1
,
0
)
D
,(
1
,
1
)
D}
LSP
:{}
We assume that the initial value of
n
is transmitted to the decoder. This allows us to set the
threshold value at 16. Upon receiving the results of the first pass (10000000), we can see that
the first element of the LIP is significant and positive and no other coefficient is significant
at this level. Using the same reconstruction procedure as in EZW, we can reconstruct the
coefficients at this stage as
