2
$\begingroup$

I am searching for a citation of a formula that calculates the proportion of true (1) outcomes in the corresponding truth table of a boolean function. Searching a little bit in the Cryptography literature, I found that the hamming weight of a boolean function is defined as the number of $1$'s, so it is close to the metric I am referring to. I have also seen this metric/property mentioned as 'truth density' in Wolfram, see an example.

Has anybody used this formula in a paper before ~2000-2010s? (a recent paper that defines it as bias is this one). Or maybe provide a proper (older) publication to cite for the hamming weight?

$\endgroup$
2
  • $\begingroup$ What is the formula? $\endgroup$
    – Myath
    Jan 19, 2021 at 6:04
  • $\begingroup$ Well, given the hamming weight of a boolean function $hw(f)$ that counts the number of $1$'s in the truth table, the truth density is $hw(f)/2^n$ $\endgroup$
    – John
    Jan 19, 2021 at 15:02

3 Answers 3

3
$\begingroup$

The truth density $p$ is arguably the same concept as the bulge to 0 $b$ of a Boolean function as $b=1-2p\iff p=(1-b)/2$. The bulge leads to cleaner formulae in many cases though. The language of bulges was common at Bletchley Park. Do you count the General Report on TUNNY as a 1945 or a 2015 publication?

$\endgroup$
3
  • 1
    $\begingroup$ nice. I thought it might have dated to that period of Turing and I.J. Good etc, but did not know a reference. $\endgroup$
    – kodlu
    Mar 12, 2021 at 10:48
  • $\begingroup$ @kodlu Here's a quote from Whit Diffie's intro. "Had I been asked, prior to reading the General Report on Tunny, when and where the bulge had first appeared, I would probably have said in the early 1950s [...] It was therefore an exciting discovery to find the term and concept of the bulge at Bletchley Park in the mid 1940s" $\endgroup$
    – Daniel S
    Mar 12, 2021 at 11:48
  • $\begingroup$ Wow, thanks for the book and the historical lessons going along with it! $\endgroup$
    – John
    Mar 13, 2021 at 9:50
0
$\begingroup$

It turns out that truth density is very closely related to the bias $p$ defined by Kauffman in his book: "The Origins of Order" (1993). It is similarly defined there as the probability that the output of a boolean function is $1$ so it should be ok as a citation.

In the Cryptographic community, the closet (and oldest) I could find is this 1997 paper which defines something really close to truth density - the authors and call it correlation and is derived using the polar boolean function form (nice stuff :)

$\endgroup$
0
$\begingroup$

These ideas are much older.

The Walsh-Hadamard basis is the basis for first order Reed Muller codes, and can be used to obtain the sylvester form of the Hadamard matrix. Reed-Muller codes were invented independently by Irving S. Reed and David Muller in the mid 1950s.

Reed (and Muller) used the Boolean function formulation back then, and related it to Hamming weight of the truth table of the function. In the same paper Reed also invented the majority logic version of the Fast Hadamard Transform, which was eventually used to decode the first order Reed-Muller code, deployed in the Mariner spacecraft in the 1960's by NASA, to transmit images from Mars to Earth.

  1. Reed, Irving S. "A class of multiple-error-correcting codes and the decoding scheme". Transactions of the IRE Professional Group on Information Theory. 4 (4): 38–49, 1954.
  2. Muller, David E. (1954). "Application of Boolean algebra to switching circuit design and to error detection". Transactions of the I.R.E. Professional Group on Electronic Computers. EC-3 (3): 6–12

Paul Green from JPL used the "real-valued soft decision" version of the Fast Hadamard transform, dubbed the Green Machine, which does not quantize but uses received integrated real-valued signal amplitudes directly.

As for specific cryptographic literature mention, in Sol Golomb's book "Shift Register Sequences", Aegean Park Press, 1967 a reference is made to Golomb's 1950's reports on sequences and randomness properties. The idea of balance (unbiased) of a sequence or the associated boolean function is already present there. Those are mentioned by Sol Golomb in the Preface to his book, including:

  1. "Sequences with Randomness Properties," Martin Co., June, 1955;
  2. "Nonlinear Shift Register Sequences, " JPL, October, 1957;
  3. "Structural Properties of PN Sequences, " JPL, March, 1958;
$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the references and reading material! It's nice to see that my intuition was correct: these ideas are certainly very old! $\endgroup$
    – John
    Mar 13, 2021 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.