Browse Prior Art Database

Computational Algorithms to Calculate or Approximate the Average Hamming Distance Between a Uniformly Distributed Variable and the Results of Various Arithmetic/Logic Operations on This Variable

IP.com Disclosure Number: IPCOM000146823D
Publication Date: 2007-Feb-24

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed are methods for algorithms (implemented in software or hardware, or a combination of both) for: 1. Calculation of the average Hamming distance between a uniformly distributed variable and the sum of this variable with a constant. The output of the algorithm is exact, as formally proved in this paper. 2. Approximation of the average Hamming distance between a uniformly distributed variable and the product of this variable with a constant. This algorithm is a heuristic; no formal proof neither a measure of the quality of approximation is described in this paper, besides experimental results. Some simpler cases of the Hamming distance between a uniformly distributed variable and the result of arithmetic/logic operations made upon this variable, which can be calculated by a simple formula.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 5% of the total text.

Computational Algorithms to Calculate or Approximate the Average Hamming Distance Between a Uniformly Distributed Variable and the Results of Various Arithmetic/Logic Operations on This Variable.

Disclosed are methods for algorithms (implemented in software or hardware, or a combination of both) for:

1.      Calculation of the average Hamming distance between a uniformly distributed variable and the sum of this variable with a constant. The output of the algorithm is exact, as formally proved in this paper.

2.      Approximation of the average Hamming distance between a uniformly distributed variable and the product of this variable with a constant. This algorithm is a heuristic; no formal proof neither a measure of the quality of approximation is described in this paper, besides experimental results.

3.      Some simpler cases of the Hamming distance between a uniformly distributed variable and the result of arithmetic/logic operations made upon this variable, which can be calculated by a simple formula.

Background

Hamming distance [‎5] is used in a variety of areas, such as communication [‎5,‎6], cryptographic [‎9], hashing [‎12], compression [‎12,‎13], and artificial intelligence learning systems[‎8,‎12]. In the last two decades an increasing interest arose in the use of Hamming distance for estimating the power consumed by digital circuits [‎1,‎2,‎3,‎4,‎7,‎9,‎11].

For such kind of estimations, it is often required to give an a-priory expected value (average) for the Hamming distance between the input and output of an arithmetic/logic operation, when the input is not known in advance, but rather assumed to obey to some statistical distribution. In this paper, we focus only on the case of a uniformly distributed variable input.

Novel contributions of this paper

Existing statistical works that refer to Hamming distance expectation values, do not attack computer-like arithmetic operations, addition and multiplication in particular. Texts like Chang and Pedram [‎2] leave the problem at high-level description, but give no particular-case solution. Hence, the algorithms for computations of the average Hamming distance between X and X+q, and between X and X*q, when X is a random, uniformly distributed variable in {0,1}N, are novel.

Probably some of the simple results and the sub-parts of the algorithms (such as the identification of a repeating pattern) are not novel.

Advantages of the proposed algorithms

The alternative of explicit calculation (sum all 2N cases) is obviously non practical for large N (even N=32 is too much). If one ignores the correlation between x and y=x+q, and compute E(XQY) as if X and Y are independently distributed uniformly, s/he would reach dN(q) = E(XQY) @ N/2, but this estimation is extremely poor, especially for small q. Similarly, if one ignores the correlation bet...