Int. J. Communications, Network and System Sciences, 2011, 4, 345-350
doi:10.4236/ijcns.2011.45039 Published Online May 2011 (http://www.SciRP.org/journal/ijcns)
Copyright © 2011 SciRes. IJCNS
Permutation and Complementary Algorithm to Generate
Random Sequences for Binary Logic
Jie Wan, Jeffrey Z. J. Zheng
School of Software, Yunnan University Kunming, Ku nming, China
E-mail: {wanjiech, conjugatesys}@gmail.com
Received December 15, 2010; revised March 23, 2011; accepted April 3, 2011
Abstract
Randomness number generation plays a key role in network, information security and IT applications. In this
paper, a permutation and complementary algorithm is proposed to use vector complementary and permuta-
tion operations to extend n-variable Logic function space from functions to configurations
2
2n2
22
nn
!
for variant logic framework. Each configuration contains functions can be shown in a
2
2n11
22
22
nn
matrix. A set of visual results can be represented by their symmetric properties in W, F and C codes respec-
tively to provide the essential support on the variant logic framework.
Keywords: Logic Function, Permutation and Complementary, Variant Logic, Symmetric Distribution,
Random Sequence
1. Introduction
Random numbers play an important role in many net-
work protocols and encryption schemas on various net-
work security applications [1], for example: digital sig-
natures, authentication protocols, key generation for PKI,
RSA/AES [2], nonce frustrate, symmetric stream encryp-
tion. A better random number algorithm will enhance
encryption schemas, to do other applications. To satisfy
different requirements, the NIST has published a series
of statistical tests as standards [3] to determine whether a
random number generator is suitable for a cryptographic
application. After using the vector complementary and
the permutation operations on binary logic, the variant
logical framework extends the traditional Logic function
space from functions to configurations
[4]. Under the new extension conditions, it is possible to
use simple transformation to generate huge numbers of
random sequences for future app lications.
2
2n2
22
nn
!
Permutation and complementary algorithm is de-
scribed in the paper to express different random proper-
ties through a series of binary image sequences under-
taken typical recursive ope rations.
2. Method
Cellular automata perform a natural way to generate
random sequence. The principle of binary cellular auto-
mata [5] [6] can be explained by an example as follow:
First, a sequence 001100 and a func tion f:
000,01 1,101,110 are selected.
Second, the sequence can be decomposed from left to
right. The last bit is composed to th e first bit
001100 00,01,11,10,00,00
001100 010100
2
2n2
22!
nn
Third, according to the decomposed sequences and the
generating function , a new sequence 010100 can be gen-
erated. i.e.:
f:
Followed the algorithm, the space of the generation
function can be extended further; large numbers of ran-
dom sequences can be generated. This mechanism can
increase the complexity of code-breaking.
In variant logic framework, the logic function space
has been extended from to by the per-
mutation and the complementary operations.
In 2 variable functions of cellular automata, there are
16 generated functions. And the 16 functions can be de-
scribed in a truth table (Figure 1(a)) with 16 entries.
2.1. Permutation Operation
The bit string of states
00,01,10,11 in generating
function can be converted to decimal number
0,1,2,3 .
An example in Figure 1(b) is shown to permute 3210 to
Int. J. Communications, Network and System Sciences, 2011, 4, 345-350
doi:10.4236/ijcns.2011.45039 Published Online May 2011 (http://www.SciRP.org/journal/ijcns)
Copyright © 2011 SciRes. IJCNS
(a) (b)
Figure 1. Permutation example, (a) The Truth Table of 3210; (b) The Permutation Table of 1320.
1320 of the table.
2.2. Complementary Operation
In the complementary operation, the complementary
vector
is applied operate to the truth table.
It can be describe as
,1y
,0
yy
In 2-variable variant logic,
is a binary sequence of
4 bits in
. In the example the original
table is
0000, ,1111
1111
and shown in Figure 2(a) the given
1100
to Table 2 can be d esc ribed as
. Under such operation, the sequence
values of state 1 and 3 columns are invariant. But the
values of columns whose index is 0 and values of the
permutation sequence in state 2 and 0 are changed to
their revised values respectively.

1100 11 0 0
13201 320
After the complementary operation, Figure 2(a) chan-
ges to Figure 2(b).
2.3. Visualization
For function f applies once applied again the sequence
001100 output 010100.then applied again the 010100 to
output 111100.For such binary sequence, select black for
1 and white for 0 to generate the visual patterns as fol-
lows (Figure 3).
2.4. Matrix Representation
For example, (Figure 2(b)) the truth value of 3th func-
tion is 1010. It can be converted to a binary coordinate
10 10 distinguished Left two and tight two bits re-
spectively. So the decimal coordin ate is 22 . Then the
(Figure 2(b)) can be converted to Table 1.
Under such converting the 2D matrix can be repre-
sented in Table 2.
3. Algorithm and Properties
3.1. Permutation and Complementary Algorithm
Using permutation and complementary operations, an
algorithm is extended to express the n-ary variant logic
functional space.
J. WAN ET AL.347
Algorithm: Permutation and Complementary:
Input: variable n Output: a set of truth table of P
,
2n
PS
2
2
n
B
,
.

(a) (b)
Figure 2. Complementary Example, (a).The Permuatation Table of 1320(1111); (b).The Complementary Table of 1320(1100).
Method:
Step 1. Initial

1 0
000 0
T21
n

Step 2. Generate a perm utation P for T
Step 3. From
2
to 111 ··· 1 do vector
complementary operation.
Step 4. Any new permutation?
Yes go to Step 2.
Step 5. End
where S(N) is a symmetry group with N member and
B
2
is a M variable Boolean structure with
members.
3.2. Representation Scheme
Every truth table has a 2D matrix to arrange visual re-
sults of random sequen ce. The ,
X
Y is the coordinate
to allocate each visual result. So for n-ary logic function
space, the 2D matrix has a size of 2shown
(Table 3).
11
22
2
nn
3.3. W, F and C Code
Three coding schemes can be distinguished in the algo-
rithm.
W code [4] is a binary sequence of bits. It sepa-
rates into two parts 2n
10
JJ 1
2n
1
. Each part has bits
F code is a subset of W code. And it is a symmetry
code. In F code, if the I-th Meta state in
J
is 1 or 0, the
I-th meta state in 0
J
is the negative state. 1
If a code is F code and the I-th meta state in
J
have
the same value. Besides four corners of its matrix are
included in
0, ,,1
x
x, it is C code [4].
E.g. 3210111001 00 is an element of W code.
In the sequence 1 isn’t the negative sequence of 3. And
the 0 isn’t also the negative seque nce o f 2.
Copyright © 2011 SciRes. IJCNS
J. WAN ET AL.
348
Figure 3. Visualize the Random sequence.
Table 1. Coordinate map of 1320(1100).
1 1 0 0
J P Status
1 3 2 0
01 11 10 00
Transformed
bracket
0 0 0 1 1 <0,3>
1 0 0 1 0 <0,2>
2 1 0 1 1 <2,3>
3 1 0 1 0 <2,2>
4 0 0 0 1 <0,1>
   
   
13 0 1 0 0 <1,0>
14 1 1 0 1 <3,1>
15 1 1 0 0 <3,0>
Table 2. 2D Matrix of the 1320(1100).
<0,0>
5 <0,1>
4 <0,2>
1 <0,3>
0
<1,0>
13 <1,1>
12 <1,2>
9 <1,3>
8
<2,0>
7 <2,1>
6 <2,2>
3 <2,3>
2
<3,0>
15 <3,1>
14 <3,2>
11 <3,3>
10
Table 3. 2D Matrix for n-ary logic functions.
<0,0>   1
2
0,2 1
n
<1,0>   1
2
1, 21
n
 
1
2
22,0
n 
11
22
22,21
nn

1
2
21,0
n 11
22
21,21
nn

32 011110 0001 is an F code. It has the symmetry
property. In the sequence 0 is the negative sequence of 3
and 1 is the negative sequence of 2.
132001 1110 00 is a C code. It has the symmetry
property of F code. And four comers of 1320’s matrix
are included in
0, ,,1
x
x.
The further definition of W, F and C code can be
found in the [4].
From the exhaustive of the binary variant function
space, the number of W, F, C code in binary variant
function space [7]shown in Table 4.
4. Coding Simples
W Code:
Permutation sequence: 3210
: 1011 The value of
F Code:
Permutation sequence: 3201
: 1111 The value of
C Code:
Permutation sequence: 1320
: 1100 The value of
5. Result Analysis
In Figure 4, W code is shown a general code. Majority
W code doesn’t have apparent symmetry property. W
code covers all the code space which form from binary
input variable. These properties can be seen in Figure 4.
All the F codes have overall symmetry in 2D distribu-
tion. Obvious symmetry among functions in the 2D ma-
trix can be observed in Figure 5.
Simple is shown in a C code in Figure 6. It is a small
set of F code with complete symmetry property, C code
have the four constant vertex property. The group of the
four vertex in C code are located by 0, 15, 10, 5 func-
tions respectively.
In the n-ary logical function permutation and comple-
mentary algorithm, the permutation is operated for ;
the complementary exhaustive needs operation for
each permutation operation. A total of computational
complexity of an n-ary variant logical function using
Permutation and Complementary algorithm is
2!
n
2
2n
2
2!2n
n
O.
6. Conclusions
Copyright © 2011 SciRes. IJCNS
J. WAN ET AL.
Copyright © 2011 SciRes. IJCNS
349
A permutation and complementary algorithm has been
proposed for n-ary logical function. And sample results
are visualized. The visual results of W, F and C code in
the variant and invariant properties support the variant
Code System No
W 384
F 128
C 16
Table 4. The number of W, F and C code in 2-ary variant
functional space.
Figure 4. The 2D matrix diagram and the visual result of 32101011.
Figure 5. The 2D matrix diagram and the visual result of 32101111.
J. WAN ET AL.
350
Figure 6. The 2D matrix diagram and the visual result of 13201100.
logic system through experimentation to use an algo-
rithmic mechanism to generate a series of huge random
number sequences.
7. References
[1] W. Stallings, “Cryptography and Network Security: Prin-
ciples and Practice,” Prentice Hall, 2005.
[2] J. Soto and L. Bassham, “Randomness Testing of the
Advanced Encryption Standard Finalist Candidates,” Na-
tional Institute of Standards and Technology (NIST),
2000.
[3] National Institute of Standards and Technology (NIST),
“Random number generation,” 2008. Internet Avail- able:
http://csrc.nist.gov/groups/ST/toolkit/rng/index.html
[4] J. Zhi, J. Zheng and C. H. Zheng, “A framework to ex-
press variant and invariant functional spaces for binary
logic,” Frontiers of Electrical and Electronic Engineering
in China, Vol. 5, No. 2, 2010, pp. 163-172.
[5] S. Wolfram, “Theory and Applications of Cellular Auto-
mata,” Singapore: Word Scientific, 1986.
[6] S. Wolfram, “Cellular automata as models of complex-
ity,” Nature, Vol. 311, 1984, pp. 419-424.
[7] J. Wan and J. Zheng, “Showing Exhaustive Number Se-
quences of Two Logic Variables for Variant Logic Func-
tional Space,” Proceedings of Asia-Pacific Youth Con-
ference on Communication (APYCC), October 2010, p. 4.
Copyright © 2011 SciRes. IJCNS