I'm afraid to look. I was up a little after 2:00 a.m. this morning when the power went out. I was really mad, because I had been typing an entry into this 'blog for about an hour, and was about two minutes away from saving it.

I really (key word here: REALLY) don't like living in this area. I have seen more power outages since I moved here four years ago than I ever did growing up in Tucson, Arizona. At least in Tucson, the power would go out for a reason (thunderstorms, drivers mating with power poles, etc.). But out here, the power just seems to quit because it feels like it.

Maybe it's tired.

Anyway, I will try to recapture the 'blog entry that I tried to post this morning. I haven't checked to see if I have lost anything else, yet - I haven't gotten up the nerve. OK, maybe I will check now.

Whew! I didn't lose any work!

I would have been a little pissed if I had lost work, especially considering what I have accomplished over the past two or three days. I feel like I have created a whole new science. Well, I know it's not new - in fact, I have probably re-invented a couple of wheels. But it's just like me to re-invent wheels, because I am always hopeful that I will see something that the original creator missed along the way and wind up with a better wheel. Mostly, I just wind up wasting my time (although I do learn a lot in the process).

It all started with the one last critical issue on my issues list for my RC4 device. In the process of trying to determine where the problem was and how to fix it, I noticed some abnormal behavior on an unrelated issue. So, before I knew it, my issues list expanded to two items. I decided to tackle this new item, first, because I thought it would be easier.

HA HA HA HA HA HA HA HA HA HA HAAAAAAAAAA!!!!! Don't make me cry.

It is interesting that I had been thinking about bits and Boolean logic, etc., a couple of days before this new issue popped up - it is as if I somehow knew what was coming.

During the course of RC4's development, I have not created a concise reference document that consolidates all the features into one quick-reference chart. Due to feature creep, this information was not known, fully, at design time, so new conditions and new modes have been added along the way. I had failed at previous attempts to create a table listing all of the possibilities, but now it appeared it was something I had to do in order to make progress on this issue. So, I set out to reverse engineer my own creation, and now I have a better and clearer perspective on this thing than I ever have before.

It became important to attain this clarity, because there is one key routine at the very heart of RC4 that determines how the device behaves depending on current conditions. There is one of eight possible base modes of operation that RC4 can be set to at any given time (R/C, R/C Fixed, R/C FailSafe, R/C Presets, Command, Command Override, Command FailSafe and Command Protected). If you want to know more about what these modes are and what they mean, you can read all the gory details in the online docs for Revision F on the web site.

Each of these eight modes are augmented by the state of other features of the device, including the Fail-Safe mechanism, whether or not signal is currently detected, and whether noise rejection is enabled. Depending on these conditions, RC4 selects one of four tables as its source for input signal data. In fact, that is the sole function of this one key routine - to select the proper signal table based on current conditions.

In all, there are six bits that describe the possible states in question at any given time. Therefore, there are 64 unique conditions, and the proper signal source table had to be selected for each of those conditions. The code that was in place worked except for one or two conditions. After attaining this new perspective, I was amazed it was working as well as it was - I had done a good job of distilling the code down to a bare minimum without the help of a truth table. But without a truth table, it was a nightmare to try to figure out how to change the code to pick up that last incorrect state. And three attempts to change the code, failed.

So I embarked into the world of Boolean Algebra. My skills were rusty and weak, but I dove right in. I created a truth table with 64 "input" bits and four "output" bits to represent the logic needed for a fully functional routine. But in my efforts to simplify the resulting Boolean equations, I kept making mistakes and after a few tries, still did not have the correct equations.

So then I began to study the bits to see if there was some way I could distill the table down to a simplified form without the use of Boolean Algebra. This is where the [re-]invention of the wheel began. I don't know if I have re-invented a wheel here or not or if my algorithm is unique, but after a few false starts and dead ends, I began to feel as if I was just wasting my time again. But I eventually stumbled onto an approach along the way that led to success!

I now have a working algorithm (and some Delphi code) that will take a truth table and spit out the simplified Boolean equation(s) that describe it. I call it the "Bit Sifter." It works with any number of inputs and outputs (though currently with a 32-bit limit). I was able to use a couple of tricks the greater simply my immediate problem, which helped tremendously. First, two of the signal tables that RC4 chooses from are kind of shadows of each other, so I reduced the truth table output possibilities from four to three, as there was only one simple condition to check afterward to see if the selected signal table really needed to be the other signal table (otherwise, I actually would have needed to add a seventh input, with 128 possible permutations).

The other trick was based on the fact that the outputs of the truth table were exclusive - in other words, only one output was selected for any given input - and the fact that EVERY input condition resulted in an output. This enabled me to solve for two outputs, only, because if neither of the two produced an output, I could deduce that the third output must be the chosen one (essentially tying the two outputs to a NOR gate to get the third output). Therefore, I was able to pick the two simplest Boolean equations and model the code after them, leaving the third output condition as the default selection.

As a result of all my hard work, I was able to distill this truth table down to 25 instructions in the microcontroller code. It is amazing to me that 64 possible conditions with four possible outputs can be represented by only 25 lines of code! Not just 25 lines of code, but 25 INSTRUCTIONS!

I am now looking at the possibility of having this algorithm spit out optimized microcontroller code as well - something that I believe could be adapted to spit out code for any language, even Verilog or VHDL, or even spit out a schematic of logic gates. I am also looking for ways to improve the algorithm to determine the absolute simplest Boolean equation (I am exploring if there are conditions where a false table with an inverted output may produce a more simplified equation - you know, the other side of the bit, like I mentioned in an earlier 'blog entry).

Anyway, it is a whole new arena to explore. When I first learned Boolean Algebra so many years ago, I wanted to write software that would reduce the equations to their simplest form, but I just was never able to figure it out. And now I have it! I just wonder if maybe there is some way to make some money here. Perhaps a little utility to assist designers (hobbiests?) in hardware design, especially with the rising popularity of FPGAs (now that they're starting to become affordable to hobbiests).

Well, it's cool, and I'm happy. Now I just need to assemble my code and see if it actually works. I haven't done that, yet. But I am confident that it will work. At least, it will work according to the truth table I put togheter - this much I know. And if the truth table is wrong, at least now I have the tools to help me fix it!

YIPPIE!

I thought it might be interesting to show the code that resulted from this, so here it is:

        MOVLW   ITABLE              ; Default = ITABLE

        BTFSC   CHANNELX,cfCOMMAND  ; B

        GOTO    STCM                ; B+

        BTFSC   PSTAT,psFAILSAFE    ; B- : E

        GOTO    STRCFS              ; E+

        BTFSC   PSTAT,psLOCKOUT     ; E- : A

        BTFSS   AFLAGS,afSIGNAL     ; A+ : F

        GOTO    STIT                ; A- & F-

        GOTO    STOT                ; F+



STRCFS: BTFSC   CHANNELX,cfFAILSAFE ; E+ : C

        GOTO    STCT                ; C+

        BTFSS   CHANNELX,cfFIXED    ; C- : D

        GOTO    STIT                ; D-

                                    ; D+

STOT:   MOVLW   OTABLE              ; OTABLE 

        GOTO    STOEX               ;



STCT:   MOVLW   CTABLE              ; CTABLE

        GOTO    STOEX               ;



STCM:   BTFSS   PSTAT,psLOCKOUT     ; B+ : A

        BTFSS   CHANNELX,cfOVERRIDE ; A- : D

        GOTO    STCT                ; A+ & D-

        BTFSS   AFLAGS,afSIGNAL     ; D+ : F

        BTFSC   PSTAT,psFAILSAFE    ; F- : E

        GOTO    STCT                ; F+ & E+

                                    ; E-

STIT:   BTFSC   CHANNELX,cfPASSTHRU ; ITABLE

        MOVLW   PTABLE              ; PTABLE

The nomenclature in the comments is something I created to help me keep understand what is going on. The letters (A through F) represent the six inputs to the truth table, and the + and - indicates which branch of the decision tree the code is following. Where I have indicated a letter with no + or -, the instruction is testing the input that is represented by that letter. By the way, only the code needed to select the proper table is shown here - the branch to STOEX saves the selection into a register and returns to the caller...just in case you were wondering.

The point here is not to understand my work, but to show the small size of the code that resulted in my efforts. For what it's worth. "ITABLE" and "PTABLE" are those shadow input tables I mentioned, so the last test in the code checks to see if the ITABLE selection really needs to be PTABLE. That was the seventh input that I excluded from the truth table.

Oh, and if you want to see the truth table, here it is:

ABCDEF|CIO

------+---

000000|010

000001|010

000010|010

000011|010

000100|010

000101|010

000110|001

000111|001

001000|010

001001|010

001010|100

001011|100

001100|010

001101|010

001110|100

001111|100

010000|100

010001|100

010010|100

010011|100

010100|010

010101|100

010110|100

010111|100

011000|100

011001|100

011010|100

011011|100

011100|010

011101|100

011110|100

011111|100

100000|010

100001|001

100010|010

100011|010

100100|010

100101|001

100110|001

100111|001

101000|010

101001|001

101010|100

101011|100

101100|010

101101|001

101110|100

101111|100

110000|100

110001|100

110010|100

110011|100

110100|100

110101|100

110110|100

110111|100

111000|100

111001|100

111010|100

111011|100

111100|100

111101|100

111110|100

111111|100



Inputs:

(A) psLOCKOUT  - Lockout engaged (noise rejection)

(B) cfCOMMAND  - Command or R/C mode selection     (mode bit 2)

(C) cfFAILSAFE - Channel responds to FailSafe      (mode bit 1)

(D) cfFIXED    - For R/C Fixed or R/C Presets mode (mode bit 0)

(E) psFAILSAFE - FailSafe engaged

(F) afSIGNAL   - Valid signal(s) received



Outputs:

(C) CTABLE - Command Table

(I) ITABLE - Input signal table

(O) OTABLE - Output signal table

And here is the resulting output from my algorithm:

---- 001 OTABLE ----

x0011x

10xx01  

= /B/CDE + A/B/EF



---- 010 ITABLE ----

000000

0000x1

x00010

00x10x

00100x

01x100

10xx00

100011

= /B(/D(/A(/C + C/E) + A(/C(/F + EF) + C/E/F)) + D(/A/E + A/E/F))



---- 100 CTABLE ----

x01x1x

01x0xx

01x1x1

01x110

11xxxx  

= /BCE + B/A(/D + D(F + E/F)) + BA

As you can see, the resulting equation for ITABLE was really ugly and would have completely cluttered up my code. It was much easier to simply solve for CTABLE and OTABLE and then select ITABLE only if neither of the other two were selected.

And here is the decision tree (using my nomenclature) from which I implemented the code:

Decision Tree:



x01x1x  B-E+C+      = CTABLE

x0011x  B-E+C-D+    = OTABLE

10xx01  B-E-A+F+    = OTABLE

11xxxx  B+A+        = CTABLE

01x0xx  B+A-D-      = CTABLE

01x1x1  B+A-D+F+    = CTABLE

01x110  B+A-D+F-E+  = CTABLE

Everything Else     = ITABLE

I have not yet automated the process of creating a decision tree, but I have an algorithm worked out in my head to do it. That is my next task after testing RC4 with the new code.