__ Page 01 of 3 __

The method describes a new variation of Hoffman coding. The novelty is in the specific way how the code words are assigned to the vectors.

Let φ, φ_{0}, φ_{1} ... are logical variables, and F_{1},F_{2},...,F_{16} are binary logical functions. The table show all binary logical functions:

Let φ^{0} = φ, φ^{1} = ¬φ. Let's consider formula:

for j ϵ I where I = {1,2,...,16}, i_{k }ϵ {0,1}, k=0,1,...,n-1.

Let j ϵ I. For some vectors (i_{0},i_{1},...,i_{n-1}), i_{k }ϵ {0,1}, k=0,1,...,n-1 formula (1) can be tautology

(i.e. when φ = 0 (or φ = 1 respectively) formula (1) is true). Analysis of this formula can be done for any positive integer and for any logical function F_{j}, j = 1,2,...,16 [*].

Proposed algorithm:

Let's consider two logical functions: F_{10} and F_{14 } and a Boolean vector

v = (v_{0},v_{1},...,v_{n-1}). For the formula (1) and the vector v the definition of F_{j}(v) is

The algorithm operate on data in a binary form. So we should transform the data to this form. Moreover this method of data compression can be used to already compressed data.

Assumptions:

- the data are presented in a binary form.

- the number of bits can be divided by 4. If not then we do not code last 1,2 or 3 bits and leave it uncoded.

- v_{i}, i=0,1,...,15 are binary vectors of length 4 (order is given by positive integer numbers presented as Boolean vectors of length 4 so v_{0} = 0000, v_{1} = 0001,...,v_{15} = 1111)

Step 1: We divide the data for blocks (or vectors) of length 4 (one by one i.e. first 4 bits create first vector, next 4 bits create next vector etc.).

Step 2: For each v_{i}, i=0,1,...,15 we put probability p_{i} of occurrence of this vector in the set of all vectors created in the step 1. Let {p_{0},p_{1},...,p_{15}} is the set of all these probabilities.

Step 3: Let p_{i_0 }≥ p_{i_1 }≥ ... ≥ pi_15 for i_j {0,1,...,15}, j = 0,1,...,15. ϵ

condition is hold: p_{i_0 }+ p_{i_1} > p_{i_10} + p_{i_11} + ... + p_{i_15}.

If yes, then the compression is possible. If not, then stop.

Step 4: We consider two permutations: σ_{1} (depend on input) is a permutation which act on the set {0,1,..,15} of indexes of vectors v_{i}. It ordered these vectors by probability p_{i }decreasing (i.e. if v_{i} has the greatest probability p_{i} then σ_{1 }(i)=0 etc.). If there exist vectors with the same probability then we consider order given by indexes of v_{i} and put consecutive values of permutation σ_{1} for all of them; σ_{2} ( not depend on input) is a

We check if the following

__ Page 02 of 3 __

permutation which act on the set {0,1,..,15} in the following way:

This permutation is directly connected to F_{10} and F_{14}. It assign the shortest codes to the vectors with the greatest probability.

Step 5: On the indexes i for i=0,1,...,15 we act by σ_{2 }(σ_{1}(i)). We consider vectors w_{i }given by w_{i}=v_{σ2 (σ}1(i)) . Now we compute F_{10}(v_{i}) and F_{14}(v_{i}) i.e. if for some vector F_{10}(v_{i}) (or F_{14}(v_{i}))

is tautology then we put 1, in another case we put 0. We assign the prefix F_{10}(v_{i}) F_{14}(v_{i}) (consist 2 values from the set {0,1}) to each vector w_{i}.

Step 6: For each vector w_{i} we create the u...