04.083GPPMobile radio interface Layer 3 specificationRelease 1998TS
The decoding algorithm, as given below, is the inverse transform of the program given in the previous sub-clause, for the specific case where the original range is a power of 2 minus 1. It is given a set of integer values W(i), and an original range R, and it builds a set of values from 0..R-1.
The program is here written so that the fact that it is the inverse of the encoding program needs no more proof.
procedure DECODE(in W : array <> of INTEGER;
out SET : SET_OF_VALUE;
in ORIGINAL_RANGE : INTEGER);
— local variables
INDEX : 1..W’SIZE; RANGE : INTEGER;
N : INTEGER;
for K in 1..W’SIZE loop
The next loop follows the tree from child to parent, from the node of index K to the root (index 1). For each iteration the node of index INDEX is tackled. The corresponding range is RANGE, and N is the value of the element in the range defined by the node.
The data are set to their initial values :
INDEX := K;
RANGE := ORIGINAL_RANGE / GREATEST_POWER_OF_2_LESSER_OR_EQUAL_TO(INDEX);
N := W(INDEX) – 1;
while INDEX>1 loop
Due to the assumption that the original range is a power of two minus one, the range for the parent node can be easily computed, and does not depend upon whether the current node is a left or right child :
RANGE := 2*RANGE + 1;
Let us note J := 2g-1, g being the generation of node INDEX. We have J = GREATEST_POWER_OF_2_LESSER_OR_EQUAL_TO(INDEX). The numbering used in the tree is such that the nodes of index J to J + J/2 – 1 are left children, and the nodes of index J/2 to J+J-1 are right children. Hence an easy test to distinguish left and right children:
if 2*INDEX <
then — left child
The next computation gives the index of the parent node of the node of index INDEX, for a left child :
INDEX := INDEX –
The next formula is the inverse of the renumbering appearing in the encoding for a left child. It gives the value of the parent node in the range defined by the grand-parent node:
N := (N + W(INDEX) – 1 + (RANGE-1)/2 + 1)
else — right child
The next computation gives the index of the parent node of the node of index INDEX, for a right child :
INDEX := INDEX – GREATEST_POWER_OF_2_LESSER_OR_EQUAL_TO(INDEX);
The next formula is the inverse of the renumbering appearing in the encoding for a right child:
N := (N + W(INDEX) – 1 + 1) mod RANGE;
F(K) := N;
A careful study will show that the programs given in the main part of the Technical Specification are equivalent to the one presented here. The main difference is the use of different remnant variables to remove most of the calls to the function giving the greatest power of 2 less than or equal to some integer.
The decoding must be terminated by the correction specific to the format.