encryptionofbinarydatausinginterlacedbin

Encryption of Binary Data Using Interlaced Binary Search (EBIBS)

Invention Title: Encryption of Binary Data Using interlaced Binary Search (EBIBS).

Invention Theme: Compression of a large group of bits to a small group of bits.

Invention Aim: Increasing storage or trasmission bandwidth irrespective of types of file.

Invention Algorithm: Interlaced Binary Search Algorithm (IBS)

Invention Advantage: Simultaneous Multiple Items Search in Binary Search Tree

Algorithm Improves: IBS improves Binary Search Algorithm

IBS searches simultaneously multiple items in the binary search tree with better run time efficiency than that of binary search algorithm that searches multiple items sequentially. IBS searches multiple items in a interwave or interlace fashion.

THEOREM I: Interlaced Binary Search will consume [5.2^(q-2)-2.q+2] trials to search out simultaneously

all 2^(q-1) leaves of a complete binary search tree of depth q formed from first (2^q – 1) natural numbers

ranging from 1 to (2^q-1).

USE OF IBS: (1) Interlaced Analog to Digital Converter (IADC), and (2) Compression of Binary Data Irrespective of Source Files.

1. Field of Invention:

The invention relates to an Encryption and Decryption Method (EDM) having a microarchitecture microprogrammed with Adaptive Delta Modulation (ADM) procedure that modulates the locus of the search path to search all quantized bytes with the Interlaced Binary Search (IBS) algorithm to store and transmit an equivalent binary code using lesser number of serial bits’ stream than that of the source binary file.

2. Background of Invention:

In digital memory or digital data communication binary number system is in use that uses bits for representation of 1 or 0. Bits are further grouped into bytes (set of 8 bits). A large number of bytes are used to store binary equivalent information in a file to be processed, stored, and transmitted by the computer system. Each byte is formed with the binary search algorithm on a search (with 8 trials) in a binary search tree of 256 nodes corresponding to decimal digits from 0 to 255. For a binary file composed of ‘nk’ bytes (8nk bits), there is requirement to store and transmit all ‘8nk’ bits.

The invention groups this ‘8nk’ bits into ‘n’ groups of ‘8k’ bits each. Each of these ‘n’ groups is termed as Quantized Bytes (Qb). The numbers corresponding to these n groups occupy into the binary search tree formed by the first 2^8k natural numbers ranging from 0 to (2^8k-1). Interlaced binary search algorithm searches this ‘n’ Qb in this binary search tree. The locus of the search path so generated is adaptive delta modulated to store and transmit.

The Interlaced Binary Search (IBS) algorithm removes the limitations of well-known binary search algorithm that are inability to search simultaneously multiple items and the limit of the search efficiency by log₂n. IBS is first used in the design of the interlaced analog to digital converter to microprogram the microarchitecture – refer http://alokeinweb.googlepages.com/interlacedadconverter

Adaptive Delta Modulation (ADM) is a scheme of differential pulse code modulation (DPCM). In DPCM, instead of transmitting a base band signal m(t) on sampling and binary coding, at each sampling time (say time k), the difference between the sample value m(k) at sampling time k and the sample value m(k-1) at time (k-1) is transmitted. Obviously this difference will call for fewer bits for transmission. On the receiving end, the addition of this difference values will regenerate the actual signal. The number of bits in DPCM can again be reduced through delta modulation (DM). In DM m(k) is compared with regenerated signal up to m^/(k-1). This comparison facilitates just single bit transmission for just two possibilities – increase or decrease regenerated m^/(k). DM has the limitation, that to go with large change in original signal there is requirement of high sampling rate; that again is limited by Nyquist rate. Nyquist rate is the minimum allowable sampling rate 2f_M for exact recovery of a band-limited signal with f_M as highest frequency spectral component. ADM overcomes this drawback on increase or decrease of quantization step size with fixed sampling rate. References:(1) Taub Herbert and Schilling Donald L. “Principles of Communication Systems” Singapore, McGraw-Hill Book Company 1986. (2)Carlson A. Bruce “Communication System” Singapore, McGraw-Hill Book Company 1986.

3. Object of Invention:

The principal object of this invention is to reduce ‘8nk’ bits of a binary file that will reduce storage size and increase transmission speed. The compression ratio (CR) that is the ratio of the number of bits after ADM to that of the original binary file comes in worst case as [(log₂n +3p)/k] where p is the average number of trials per ‘Qb’ in the locus of the search path generated by the IBS algorithm.

4.Summery of the invention:

The invention relates to an Encryption and Decryption Method (EDM) having a microarchitecture microprogrammed with Adaptive Delta Modulation (ADM) procedure that modulates the locus of the search path to search all quantized bytes with the Interlaced Binary Search (IBS) algorithm to store and transmit an equivalent binary code using lesser number of serial bits’ stream than that of the source binary file.

The invention groups the ‘8nk’ bits of any binary file containing ‘nk’ bytes in total, into ‘n’ groups of ‘8k’ bits each. Each of these ‘n’ groups is termed as quantized bytes (Qb). The numbers corresponding to these n groups occupy into the binary search tree formed by first 2^8k natural numbers ranging from 0 to (2^8k-1). IBS algorithm searches the ‘n’ Qb in this binary search tree in a single run. The locus of the search path so generated is adaptive delta modulated to store and transmit. The compression ratio (CR) that is the ratio of the number of bits after ADM to that of the original binary file comes in worst case as [(log₂n +3p)/k] where p is the average number of trials per ‘Qb’ in the locus of the search path generated by the IBS algorithm.

5. Brief description of accompanying drawing:

This complete specification enlists one (1) figure (FIGURE 1) that describes the flow chart of the microarchitecture. Different parts of the flow chart are:

Quantizer (QTZ): Groups ‘nk’ bytes of the input source file into ‘n’ Qb (quantized byte) of ‘k’ bytes each.

Adaptive Delta Modulator (ADM): Generates serial bit stream through the process of the adaptive delta modulation. It has two principal sections that are IBS and ENC described as follows.

Interlaced Binary Search (IBS): Use IBS algorithm to generate the locus of search path to search ‘n’ Qb in the binary search tree formed by the first 2^8k natural numbers from 0 to (2^8k-1)

Encoder (ENC): Encodes the locus of search path generated by the IBS.

Communication Link: Serial Storage / Transmission of the serial bit stream produced by the ADM.

Proxy-IBS: Mimics IBS of the ADM to generate ‘n’ Qb.

Dequantizer (DQZ): Serializes ‘n’ Qb generated by the Proxy-IBS and so outputs the original file.

Successive Analog Approximation (SAA): Recovers Qb in the high-level language implementation of the invention.

The Inventor(s) Name(s): (1) aloke SARKAR, (2) basudha SARKAR, (3) sila SARKAR

Aloke Sarkar's introduction: 2 Engineering Degrees - (1) Electronics & Communication and (2) computer. 2 inventions management thoughts. 7 India national level and 2 International level papers. May refer http://alokeinweb.googlepages.com/

Owner of the invention: yes. basudha SARKAR, sila SARKAR

3. Protection

Patent Application No. 486/KOL/2003

Priority: 19 September 2003

Countries where it is in force: INDIA

4. Business intention

Selling and/or Licencing

5. Contact

Name: ALOKE SARKAR

E-mail: aloke412@rediffmail.com , basudhasarkar@rediffmail.com

Tel.: 91-9778400134, 91-9937462614, 91-661-2640289

Address: C-38, SECTOR-9, ROURKELA, ORISSA, INDIA. PIN-769009