Scrambling by reversible conservative bit block automata

Michael Schreiber

Wolfram Research

Abstract

Bit Block automata return blocks of output bits for blocks of input bits. They are reversible if their rules include all possible input blocks among their output blocks. Those reversible systems conserve bit counts immediately if all their rule digits return output bits which are permutations of their input bits. Formulas for the numbers of these kinds of bit block automata are given. Scrambling of images is discussed as an example. Alternating conservation of bitcounts is implemented for byte block automata as an example for models of reversible and non-reversible bit block systems which maintain zero total average energy.

Introduction

Conserved quantities are typical for natural phenomena and thus interesting for NKS (p. 1022).

Recent demonstrations gave hex and byte machine examples for bit block automata.

This talk presents image processing experiments with conservative and alternating conservative reversible byte block automata.

Counting bit block automata

Wolfram counts reversible and conservative block automata (NKS p. 1023).

Counting generic bit block automata

Block automaton rules for m bit inputs and outputs are specified by (2^m) base (2^m) rule digits.

This definition permits ((((2^m)))^(2^m)) generic  m-bit block automata.

Manipulate[ArrayPlot[Join[1-Transpose[# &[1+IntegerDigits[Reverse@Range[0,-1+2^k],2,k]]],Reverse@Switch[t,
0,1-Transpose[# &[1+IntegerDigits[Reverse@Range[0,-1+2^k],2,k]]],
1,1-Transpose[# &[1+IntegerDigits[Range[0,-1+2^k],2,k]]],
2,1-Transpose[# &[1+IntegerDigits[RandomSample[Reverse@Range[0,-1+2^k]],2,k]]]]],ColorFunction->GrayLevel,AspectRatio->1/2,PlotLabel->ToString[k]<>"-bit blocks",Mesh->{{k},None},MeshStyle->{Red}],{{k,1,"bits"},1,8,1,Appearance->"Labeled"},{{t,1,"rule"},{0->"identity",1->"complement",2->"random"}}]

Counting reversible bit block automata

A bit block automaton rule is reversible if it specifies a different output for each possible input.

(2^m)! Reversible m-bit block automata.

Counting conservative bit block automata

The number of blocks with a given bit count is given by binomial coefficients.

Sorting bytes by bitcounts illustrates this idea behind counts of conservative rules.

Manipulate[ArrayPlot[Transpose[SortBy[# Total/@#&[1+IntegerDigits[Reverse@Range[0,-1+2^k],2,k]],Max]],ColorFunction->Hue,AspectRatio->1/4,PlotLabel->"Immediate binomial conservation among "<>ToString[k]<>"-bit rules"],{{k,2,"bits"},2,8,1}]

Generic conservative rules may use the same output for all inputs with the same bit count. The resulting count corresponds to the product of the number of b-digit numbers in a base-b positional system for all binomial coefficients b.

(∏_(k=0)^m)(((({{m}, {k}})))^((({{m}, {k}}))))  conservative m-bit block automata.

Counting reversible conservative bit block automata

A reversible bit block automaton rule is conservative if the bit counts of input and output blocks are constant.

(∏_(k=0)^m)(({{m}, {k}}))!  reversible conservative m-bit block automata.

Reversible conservative rules need different outputs for all inputs while maintaining the same bit count. The resulting rule count corresponds to the product of the factorials of the binomial coefficients b.

Counting alternating conservation rules

Alternating reversible conservers return binary complements of permuted input bits.

2 (∏_(k=0)^m)(((({{m}, {k}})))^((({{m}, {k}}))))  conservative m-bit block automata including alternating conservers.

2 (∏_(k=0)^m)(({{m}, {k}}))!  reversible conservative m-bit block automata including alternating conservers.

Permutations without fixed points are called derangements and counted by subfactorials.

!((2^m)) = Subfactorial((2^m)) reversible m-bit block automata without fixed points.

(∏_(k=1)^(m-1))!(({{m}, {k}})) = (∏_(k=1)^(m-1))Subfactorial((({{m}, {k}})))  reversible conservative alternating m-bit block automata without fixed points..

Sorting bytes by maxima of one-counts and zero-counts illustrates the idea behind counts of alternating conservative rules.

Manipulate[ArrayPlot[Transpose[# Total/@#&[1+IntegerDigits[Reverse@Range[0,-1+2^k],2,k]][[Ordering[Max[Count[#,0],Count[#,1]]&/@IntegerDigits[Reverse@Range[0,-1+2^k],2,k]]]]],ColorFunction->Hue,AspectRatio->1/2,PlotLabel->"Co-binomial convservation among alternating "<>ToString[k]<>"-bit rules"],{{k,2,"bits"},2,8,1}]

Image scrambling and unscrambling

In order to outline an image processing application its now time to focus on byte block automata

The basic idea is to process color bits of neighboring pixels by reversible byte block rules.

In order to prepare further applications in other areas the focus will be on conservative rules.

Scrambling is done and undone by a byte block automaton in the bit-tensor spanned over pixels by their concatenated color or grayscale bytes.

The unscrambling vector is found by reversing the rules for all rule digits.

Portrait example

Image byte concatenation

imimp[im_]:=Transpose[Map[Sequence@@IntegerDigits[#,2,8]&,Round[255 im[[1,1]]],{3}],{2,3,1}]

Bit vector plot

This plots 24-bit vectors for pixels as three-byte colors.

Options[atribyteplot]:={atribyteplot->{}}

atribyteplot[m24xy_,OptionsPattern[]]:=ArrayPlot[Reverse[(2^Reverse[Range[0,23]]).m24xy],Sequence@@Flatten[{ColorFunctionScaling->False,ColorFunction->(RGBColor@@(IntegerDigits[#,256,3]/255.)&),Sequence@@OptionValue[atribyteplot]}]]

Polygon skin

This utility function removes inner polygons from neighboring cuboids.

prevt[vm_]:=With[{vmu=Flatten[DeleteCases[Split[Sort[Flatten[{{#+{0,0,0},#+{0,0,1},#+{0,1,1},#+{0,1,0}},
{#+{1,0,0},#+{1,0,1},#+{1,1,1},#+{1,1,0}},
{#+{0,0,0},#+{0,0,1},#+{1,0,1},#+{1,0,0}},
{#+{0,1,0},#+{0,1,1},#+{1,1,1},#+{1,1,0}},
{#+{0,0,0},#+{1,0,0},#+{1,1,0},#+{0,1,0}},
{#+{0,0,1},#+{1,0,1},#+{1,1,1},#+{0,1,1}}}&/@(Position[vm,1]),1]]],{{{_,_,_},{_,_,_},___},{{_,_,_},{_,_,_},___},___}],1]},With[{vmupf=Union[Partition[Flatten[vmu],3]]},GraphicsComplex[N[vmupf],Polygon@Map[Flatten[Position[vmupf,#]&/@#]&,vmu]]]]

Significant bits in a portrait example

i60=imimp[];

The plot shows the most significant red, green and blue bits in the portrait.

Graphics3D[{Opacity[.25],EdgeForm[],
Red,prevt[Reverse/@Transpose/@Join[Take[i60,2],0 Take[i60,{9,10}],0 Take[i60,{17,18}]]],
Green,prevt[Reverse/@Transpose/@Join[0Take[i60,2],1 Take[i60,{9,10}],0 Take[i60,{17,18}]]],
Blue,prevt[Reverse/@Transpose/@Join[0 Take[i60,2],0 Take[i60,{9,10}],1 Take[i60,{17,18}]]]},ViewPoint->{-1,0,0}]

Visualizations of idealized image examples

Constructed configurations demonstrate how color bits are visualized in a three dimensional space over two dimensional pixel coordinates and vice versa.

Voxel bubble

An approximation of a sphere by bits at suitable positions in a three dimensional matrix..

bubble[{px_,py_,pz_},r_,{rx_,ry_}]:=Normal[SparseArray[{x_,y_,z_}/;(Norm[{x-px,y-py,z-pz}]<r)->1,{24,rx,ry}]]

Visualization in 3D

Manipulate[Graphics3D[{Thick,Red,Line[{{1,xy[[2]],xy[[1]]},{9,xy[[2]],xy[[1]]}}],Green,Line[{{9,xy[[2]],xy[[1]]},{17,xy[[2]],xy[[1]]}}],Blue,Line[{{17,xy[[2]],xy[[1]]},{25,xy[[2]],xy[[1]]}}],White,Opacity[.5],EdgeForm[],prevt[bubble[{pz,xy[[2]],xy[[1]]},r,{24,24}]]},PlotRange->{{0,25},{0,25},{0,25}},FaceGrids->{{{0,0,1},{{9,17},None}},{{0,0,-1},{{9,17},None}},{{0,1,0},{{9,17},None}},{{0,-1,0},{{9,17},None}}}],{{xy,{12,12},"position"},{0,0},{24,24}},{{pz,12,"shift along color axis"},0,24,1},{{r,5,"radius"},2,24},SaveDefinitions->True]

Color encoded pixel representation of voxels

Manipulate[atribyteplot[bubble[{pz,xy[[2]],xy[[1]]},r,{24,24}]],{{xy,{12,12}},Locator},{{pz,12,"shift along color axis"},0,24,1},{{r,5,"radius"},2,24},SaveDefinitions->True]

Code for image scrambling

Step function

The step function can be defined by computing an inner product which finds at digit codes of output blocks at resulting positions in a rule number.

byteblockfun[r_,a_]:=Partition[Partition[IntegerDigits[r[[256- Flatten[a].{128,64,32,16,8,4,2,1}]],2,8],2],2]

astep[r_,i_]:=ArrayFlatten[Partition[Partition[byteblockfun[r,#]&/@Flatten[Partition[i,{2,2,2}],2],Length[i[[1,1]]]/2],Length[i[[1]]]/2],3]

This introductory implementation is replaced by a developer function and dispatched rule tables for block patterns later.

Finding a conservative reversible rule.

randomruleselector[]:=(RandomInteger[{0,#!-1}]&/@Binomial[8,Range[0,8]])

asubbit[w_,k_,n_]:=FromDigits[Normal[SparseArray[Thread[Subsets[Range[w],{k},{n}][[1]]->1],{w}]],2]

revorder[w_]:=Reverse[Ordering[Flatten[Permutations[IntegerDigits[-1+2^#,2,w]]&/@Range[0,w],1]]];

nthp[n1_,l_]:=
Block[{k,n=n1,s=Range[l]},
(n=Mod[n,(#+1)!];
k=s[[Quotient[n,#!]+1]];
s=Complement[s,{k}];
k)&/@Reverse[Range[0,l-1]]]

reconrule[]:=With[{pers=nthp@@@Thread[{randomruleselector[],Binomial[8,Range[0,8]]}]},
(Flatten[Table[Map[asubbit[8,t-1,#]&,pers[[t]]],{t,9}],1])[[revorder[8]]]]

From and to hexadecimal representation of byte block rules

ruletohex[r_List]:=StringJoin[IntegerString[#,16,2]&/@r]

hextorule[hs_String]:=IntegerDigits[FromDigits[hs,16],256,256]

Book detail example

A byte rule

r0=hextorule["fffdfbcffed7bedcbf7e5f7c77f89e8def7df99d6f5e6e69f6eaaba3da4b9c647fedbdd5f573e359fa3b7566e64ef019ddc74f8e5d63174a5b33968c5ca84560dfeb9fbaafb6a7533fb9b599f21e0f2afc57ece1ced4aab0d395e81a1b622544b79be5a9cd71c570bc72d2834dc432501fe2b154ca981630a5a21c82e0881420f7de7b2ff36dd92deef1678b3e475a0ddb3df46a7955ac43d6567849d8a18a22bbb37a65e9c66c0e6b9a87231d4cc80676b43c94e486c209b238291846122110e7cbadc337c9cc26972e39152b5851418fa6740b933152a027a42c0a610c4808ae3a366835859181b892340313241102d1c189c007900580d042284084040100"]

hextorule[ruletohex[r0]]===r0

rb=Reverse[Reverse[Range[0,255]][[Ordering[r0]]]]

Extraction of concatenated image colors

image=imimp[];

Comparison of unscrambled and initial image.

scrambled=astep[r0,image];

unscrambled=astep[rb,scrambled];

image===unscrambled

Manipulate[Grid[{{"original","scrambled","unscrambled"},{
atribyteplot[image,#],
atribyteplot[scrambled,#],
atribyteplot[unscrambled,#]
}},BaseStyle->"Menu"]&[atribyteplot->{ImageSize->size}],{size,{Small,Medium}},SaveDefinitions->True]

Significant bits of unscrambled and initial image.

Grid[{{"original","scrambled"},{Graphics3D[{Opacity[.25],EdgeForm[],
Red,prevt[Reverse/@Transpose/@Join[Take[image,2],0 Take[image,{9,10}],0 Take[image,{17,18}]]],
Green,prevt[Reverse/@Transpose/@Join[0Take[image,2],1 Take[image,{9,10}],0 Take[image,{17,18}]]],
Blue,prevt[Reverse/@Transpose/@Join[0 Take[image,2],0 Take[image,{9,10}],1 Take[image,{17,18}]]]},ImageSize->Medium,ViewPoint->{-1,0,0}],
Graphics3D[{Opacity[.25],EdgeForm[],
Red,prevt[Reverse/@Transpose/@Join[Take[scrambled,2],0 Take[scrambled,{9,10}],0 Take[image,{17,18}]]],
Green,prevt[Reverse/@Transpose/@Join[0Take[scrambled,2],1 Take[scrambled,{9,10}],0 Take[image,{17,18}]]],
Blue,prevt[Reverse/@Transpose/@Join[0 Take[scrambled,2],0 Take[scrambled,{9,10}],1 Take[image,{17,18}]]]},ImageSize->Medium,ViewPoint->{-1,0,0}]}},BaseStyle->"Menu"]

Orbits of reversible conservative byte block rules

The group created by a reversible conservative byte block rule can be visualized by its orbits.

reconrule[]

Manipulate[SeedRandom[seed];Row[GraphPlot[Thread[Rule[Range[0,255],#]],ImageSize->{200,200}]&/@({#,Reverse[Reverse[Range[0,255]][[Ordering[#]]]]})&[reconrule[]]],{seed,0,-1+2^31,1},SaveDefinitions->True]

Reversible immediate conservers need at least two fixed points to leave empty neighborhoods empty and full neighborhoods full.

Alternating reversible conservers

Reversible alternating conservers do not need fixed points.

Positions of rule input complements

The positions of complements for inputs with the same bitcount will be used to braid reversible conservative orbits and their complements.

pos256=(Position[{10(1+Count[#,1]),#}&/@IntegerDigits[Range[0,255],2,8],10 #]&/@Range[9])[[All,All,1]]

Selection of reversible alternating conservers

Reversible alternating conservers can be generated at random by testing random vectors until finding an instance of a rule which exhausts nine isotropic sets of byte blocks by five orbits.

prealternatingloop256[]:=Sort[Flatten[Join[{{1->256,256->1}},Table[Thread[
Join[pos256[[8-k]],pos256[[2+k]]]->Flatten[birand[pos256[[2+k]],pos256[[8-k]]]]],{k,0,2}],{Thread[
Join[Take[pos256[[5]],-35],Take[pos256[[5]],35]]->Flatten[birand[Take[pos256[[5]],35],Take[pos256[[5]],-35]]]]}]]]

birand[v1_,v2_]:=
Module[{w1=RandomSample[v1],w2=RandomSample[v2]},
While[Length[prelooptest[v1,w2,v2,w1]]<(Length[v1]+Length[v2]),
w1=RandomSample[v1];
w2=RandomSample[v2];];{w1,w2}]

ufixlist[d_,p_]:=FixedPoint[If[FreeQ[#,d[[Last[#]]]],Flatten[{#,d[[Last[#]]]}],#]&,{p}]

prelooptest[v1_,w1_,v2_,w2_]:=With[{r=ReplacePart[0Range[256],Join[Thread[v1->w1],Thread[v2->w2]]]},
ufixlist[r,w1[[1]]]]

Reversal of alternating conservation rules

The reversal rule for on alternating conserver rule is found by reversing the directions of its individual bit block rules.

postaltloop[preloop_,tf_]:=Sort[Map[Partition[Partition[IntegerDigits[#-1,2,8],2],2]&,If[tf,
preloop,Reverse/@preloop],{-1}]]

alternatingpair[]:={postaltloop[#,False],postaltloop[#,True]}&[prealternatingloop256[]]

Orbits of reversible alternating byte conservers

Column[{#,"↓","consolidation","↓",Append[Take[#+Reverse[#],4],#[[5]]]},Center]&[Binomial[8,Range[0,8]]]

Reversible alternating conservers without fixed points exhaust two complementary sets of bit configurations by each orbit.

Row[GraphPlot[#]&/@alternatingpair[]]

All of the generated alternating byte conservation rules partition the state space of the byte block machine into five orbits.

Manipulate[SeedRandom[seed];Tooltip[GraphPlot[#,ImageSize->{300,300}],Grid@Partition[#/.Rule->Overscript,16]]&[prealternatingloop256[]],{seed,0,-1+2^31,1}]

Shifts between steps

Repeated application of rules generates only local modifications which step along their orbits unless the boundaries between the blocks are shifted between steps.

Manipulate[Dynamic[If[run,t=t+1,t];Graphics3D[{{Red,Blue}[[Mod[t,2]+1]],Point[Mod[t,2]/2+Flatten[Array[{##}&,{6,6,6}],2]]},PlotRange->{{0,7},{0,7},{0,7}}]],{{t,0},ControlType->None},{{run,False},{False,True}}]

Problematic consolidation of steps

Consolidation of two byte block rules requires a rule with (2^64) byte-digits to return bytes for all possible blocks of (4^3) bits.

Graphics3D[{prevt[PadLeft[Array[1&,{2,2,2}],{3,3,3}]],Opacity[.5],prevt[Array[1&,{4,4,4}]]}]

Shifts between steps

Applications of local block rules commute with shifts but reversions of evolutions have to reverse those shifts properly.

targetbyte[{rup_,ruf_},{im_,t_},targ_]:=Switch[targ,
-1,paststep[rup,{im,t-1}],
0,If[t===0,im,If[t>0,paststep[rup,{im,t-1}],futurestep[ruf,{im,t+1}]]],
1,futurestep[ruf,{im,t+1}]]

paststep[rup_,{im_,t_}]:=Switch[Mod[t,4],
0,RotateRight[im,{1,1,1}],
1,act[im,rup],
2,RotateLeft[im,{1,1,1}],
3,act[im,rup]]

futurestep[ruf_,{im_,t_}]:=Switch[Mod[t,4],
0,act[im,ruf],
1,RotateLeft[im,{1,1,1}],
2,act[im,ruf],
3,RotateRight[im,{1,1,1}]
]

Developer step function

This modified step function avoids the dot product computation of rule digit positions by using replacements after partitioning.

<<Developer`

act[im_,ru_]:=ArrayFlatten[PartitionMap[#/.ru&,im,{2,2,2}],3]

Reversible scrambling by alternating byte conservers

Scrambling steps are connected by shift steps.

Manipulation of process direction

Manipulate[
Dynamic[If[setim===0,{},Switch[setim,0,{},1,im=i60,2,im=RandomInteger[{0,1},{24,60,60}],3,im=bubble[{12,29,29},24,{60,60}]];t=0;setim=0;];If[newrule,ru=({Dispatch[postaltloop[#,False]],Dispatch[postaltloop[#,True]]}&[prealternatingloop256[]]);newrule=False,{}];If[If[rtf===Automatic,If[t===0,run=False,run],run],im=targetbyte[ru,{im,t},Switch[rtf,True,1,False,-1,Automatic,0]];t=If[rtf,1,-1,Sign[-t]]+t;sh=Not[sh],{}];Row[{Column[{Tooltip[ArrayPlot[Partition[FromDigits[#,2]&/@Partition[Flatten[If[rtf,ru[[1,1,All,2]],ru[[2,1,All,2]],If[Sign[-t]>0,ru[[2,1,All,2]],ru[[1,1,All,2]],ru[[2,1,All,2]]]]],8],16],ColorFunctionScaling->False,ColorFunction->(Hue[#/255.]&)],GraphPlot[If[rtf,ru[[1,1]],ru[[2,1]],If[Sign[-t]>0,ru[[2,1]],ru[[1,1]],ru[[2,1]]]],ImageSize->{150,150}]],Column[StringJoin/@Partition[IntegerString[FromDigits[#,2]&/@Partition[Flatten[If[rtf,ru[[1,1,All,2]],ru[[2,1,All,2]],If[Sign[-t]>0,ru[[2,1,All,2]],ru[[1,1,All,2]],ru[[2,1,All,2]]]]],8],16,2],16],BaseStyle->Small]},Center],
Column[{If[overlay,atribyteplot[BitXor[im,i60],atribyteplot->{PlotLabel->t,PixelConstrained->5}],atribyteplot[im,atribyteplot->{PlotLabel->t,PixelConstrained->5}]],Row[{Total[Flatten[im]],Total[Flatten[1-im]]},"\t"<>":"<>"\t"]},Center]},"\t"]],
{{im,i60},ControlType->None},
{{ru,{Dispatch[postaltloop[#,False]],Dispatch[postaltloop[#,True]]}&[prealternatingloop256[]]},ControlType->None},
{{rtf,False,"direction"},{False->"-1",Automatic->"0",True->"1"}},
{{run,False,"iterate"},{False->"stop",True->"go"}},
{{newrule,False,"new rule"},{False,True}},
{{overlay,False,"Xor image"},{False,True}},
{{sh,False},ControlType->None},
{{t,0},ControlType->None},
{{setim,0,"reset"},{0->"keep",1->"portrait",2->"new random image",3->"bubble"}},SaveDefinitions->True]

The hexadecimal represents the rule. The two numbers at the bottom count 0-bits and 1-bits.

Constant zero total energy interpretation

An alternating conserver toggles the number of 0-bits and 1-bits by each application of its rule.

Replacing 0-digits by -1-digits reduces the total digit energy of consecutive conserver steps to 0.

Alternating conservation models may thus bootstrap idealized big bangs from nothing.

All reversible alternating conservers inherit this constant zero total energy feature.

Perspectives

Autonomous selection of rules according to local density or configuration would remove the need to specify particular rules. Multinomial enumerations and direct constructions for other kinds of block automata provide could such perspectives. Further constructions or searches might find ways to emulate glider like structures or new kinds of wire worlds by reversible alternating conservers.

Application perspectives include scrambling of images by arrays of simple processors.

Conclusion

Pairs of reversible rules which specify immediate and alternating conservation of bitcounts have been counted and generated at random. 

The examples showed how bit block image scrambling permits partial recognition of image contents but scrambles details among neighboring pixels and along concatenated color channel bit vectors of pixels.

Links

Block Cellular Automata (NKS p. 1023)

Conservative Byte Drift Machine

Finite Group

Group Orbit

Subfactorial