Intrinsic order, lexicographic order, vector order and hamming weight

Abstract

To compare binary n-tuple probabilities with no need to compute them, we have defined a partial order relation on the set {0, 1}n of all binary n-tuples: The so-called intrinsic order relation. In this paper, some properties of the intrinsic ordering are derived. These properties involve the lexicographic (truth-table) order in {0, 1}n, the vector order defined between the vectors of positions of 1-bits of the binary n-tuples, and the number of 1-bits in the binary n-tuples (i.e., the Hamming weights). These results are illustrated through simple examples and the intrinsic order graph.