Browse Prior Art Database

Generalization of BLF compression by prefix permutation

IP.com Disclosure Number: IPCOM000234179D
Publication Date: 2014-Jan-16
Document File: 7 page(s) / 149K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is an prefix algorithm for compressing a binary data by using untypical representation of special logical formulas and some prefix permutation.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 19% of the total text.

Page 01 of 7


1. Abstract:

Disclosed is an prefix algorithm for compressing a binary data by using untypical representation of special logical formulas and some prefix permutation.


2. Summary:

We present the generalization of data compression method by binary logical function (BLF) which was considered in disclosure paper "Data compression method by binary logical functions" [*] . We consider the same data compression method, but with additional steps in algorithm. By analysing and using representation of special logical formulas we create an algorithm which can (with some assumptions) compress binary data. Moreover, if some assumptions are hold, we can compress the same data many times and, in each iteration of algorithm, compression is better.


3. Necessary background:

In this part we describe some used definitions and terms. Moreover we present, in short form data compression method by binary logical function which will be generalized in the next part of this paper.

We put φ, φ0, φ1 ... for logical variables. Through F1,F2,...,F16 we mean binary logical functions. We use following tables to denote logical functions:

φ0 φ1 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

We put φ0 = φ, φ1 = ¬φ. Now we can consider formula:

Fj(...Fj(Fj((φi_0i_1),φi_2)...,φi_(n-1))


(1)

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

Let j ϵ I. For some vectors (i0,i1,...,in-1), ik ϵ {0,1}, k=0,1,...,n-1 formula (1) can be tautology (i.e. when we put φ = 0 (or φ = 1 respectively) formula (1) is true). Analysis of this formula can be done for any positive integer and for any logical function Fj, j = 1,2,...,16.

Algorithm BLF (without prefix permutation) proposed in [*] :

Let's consider two logical functions: F10 and F14 and a Boolean vector v = (v0,v1,...,vn-1). For the formula (1) and the vector v the definition of Fj(v) is

Fj(...Fj(Fj((φv0v1),φv2)...,φv_(n-1))

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.


Page 02 of 7

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.
- vi, 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 v0 = 0000, v1 = 0001,...,v15 = 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 vi, i=0,1,...,15 we put probability pi of occurrence of this vector in the set of all vectors created in the step 1. Let {p0,p1,...,p15} is the set of all these probabilities.

Step 3: Let pi_0 ≥ pi_1 ≥ ... ≥ pi_15 for i_j {0,1,......