J.4 Encoding algorithm

04.083GPPMobile radio interface Layer 3 specificationRelease 1998TS

The choice is done recursively as given by the following programs, written in ADA:

Let us define the recursive procedure:

procedure ENCODE_SUBTREE(in INDEX : INTEGER;

in SET : SET_OF_VALUE;

in RANGE : INTEGER);

This procedure is given a set of integer values and an index. It chooses one of those values and computes the corresponding W(INDEX) (considered as a global variable), it splits the set less the value in two equal or nearly equal subsets, and calls itself recursively for each of those subsets, with suitable INDEX.

Assumption: all values in SET lie (inclusively) between 0 and RANGE-1, and they are all distinct.

As written, the program does not assume special values for the range. With a range such as 2k-1, some expressions can be simplified.

Declarative part:

INDEX_IN_SET : INTEGER;

begin

First the program tests the leaf conditions :

if SET’SIZE=0 then

W(INDEX) := 0;

return;

elsif SET’SIZE=1 then

W(INDEX) := 1 + SET(1);

return;

end if;

The following program finds a value in the set such that exactly (SET’SIZE-1)/2 values from the set are between this value plus 1 and this value plus half the range :

declare

N : INTEGER;

J : INTEGER;

begin

for I in 1..SET’SIZE loop

N:=0;

for J in 1..SET’SIZE loop

if (SET(J)-SET(I)) mod RANGE <= (RANGE-1)/2 then

N := N+1;

end if;

end loop;

The test compares N-1 because the possible pivot value is counted.

if N-1 = (SET’SIZE-1)/2 then

INDEX_IN_SET := I;

exit;

end if;

end loop;

end;

INDEX_IN_SET is then the index in the list of the pivot value.

The following sets W(INDEX)

W(INDEX) := SET(INDEX_IN_SET) + 1;

Then the program does the same thing for the two halves of the range delimited by W(INDEX) and W(INDEX)+RANGE/2. First the left subset:

declare

SUBSET : SET_OF_VALUE(1..SET’SIZE/2);

SUBSET_INDEX : INTEGER;

ORIGIN_VALUE : INTEGER;

begin

ORIGIN_VALUE := (SET(INDEX_IN_SET] + (RANGE-1)/2

+ 1) mod RANGE;

SUBSET_INDEX:=1;

for I in 1..SET’SIZE loop

if (SET(I)-ORIGIN_VALUE) mod RANGE) < RANGE/2 then

SUBSET(SUBSET_INDEX) :=

(SET(I) – ORIGIN_VALUE) mod RANGE;

SUBSET_INDEX := SUBSET_INDEX + 1;

end if;

end loop;

ENCODE_SUBTREE(

INDEX := INDEX +

GREATEST_POWER_OF_2_LESSER_OR_EQUAL_TO(INDEX),

SET := SUBSET,

RANGE := RANGE/2);

end;

Then the right subset:

declare

SUBSET : SET_OF_VALUE(1..(SET’SIZE-1)/2);

SUBSET_INDEX : INTEGER;

ORIGIN_VALUE : INTEGER;

begin

ORIGIN_VALUE := (SET(INDEX_IN_SET] + 1) mod RANGE;

SUBSET_INDEX:=1;

for I in 1..SET’SIZE loop

if (SET(I)-ORIGIN_VALUE) mod RANGE) < RANGE/2 then

SUBSET(SUBSET_INDEX) :=

(SET(I) – ORIGIN_VALUE) mod RANGE;

SUBSET_INDEX := SUBSET_INDEX + 1;

end if;

end loop;

ENCODE_SUBTREE(

INDEX := INDEX +

2*GREATEST_POWER_OF_2_LESSER_OR_EQUAL_TO(INDEX),

SET := SUBSET,

RANGE := (RANGE-1)/2);

end;

end ENCODE_SUBTREE;

The initial call of the procedure depends on the format. Given some set to encode, the first problem is to verify that it can be encoded, and by so doing to choose the format.

First the encoding process must find the minimum range of the set, that is to say the minimum value R such that there exists one frequency F0 in the set such that all frequencies in the set can be written (F0 + N) mod 1024, with some N, 0  N  R-1. The choice of the format depends on R and the number of frequencies : the 512 range format can be chosen only if R512, the 256 range format can be chosen only if R256, the 128 range format can be chosen only if R128.

If the chosen format is "1024 range", then the program must first check if frequency 0 is in the set. If so the F0 subfield is set to 1, and frequency 0 is removed from the set. Otherwise, the F0 subfield is set to 0. Then ENCODE_SUBTREE is called with INDEX := 1, SET set to the set of values equal to the ARFCN of all frequencies minus 1, and RANGE := 1023.

If the chosen format is "512 range", "256 range" or "128 range", F0 is chosen as ORIG-ARFCN and ENCODE_SUBTREE is called with INDEX := 1, SET set to the set of values equal to the ARFCN of all frequencies except F0, minus F0+1, and RANGE set respectively to 511, 255 or 127.