Topics

CVs coded in base 3 (ternary)

Alain LM
 

Hi All,

Doehler & Haass are using a ternary coding for CV 145-152 (Conditions for outputs)  in order to pack 4 independent values with respectively 3, 3, 3 and 6 possible values each. Using the traditional binary coding would have required 9 bits (!) with some intermediate values wasted.

In order to split the trits (ternary bits...) and display each parameter individually, it would be required to expand the 'mask' principle by creating a new qualifier - for example base="3" or base="ternary".

I don't expect this to be overly complex, however as I'm not familiar with the symbolic programming Java code, I would highly appreciate if someone could:

- either provide me with guidance which files I need to look into to implement the change,
- or implement the change.

Also I was wondering if there is a need to expand the principle to other base value such as 5 (Quinary or pental).
For base 7, I don't see much interest (not enough 7-bits in a Byte...). Other lower values are multiple of 2 or 3, so the existing mask system will be enough.

--
Alain LM

Bob Jacobsen
 

I think I can handle this as part of the binary-coded decimal case that I’m working on: Just adding the possibility of having bases other than 10.

But let me first confirm what’s needed.

You look at CV145, and see a value of 101. This is 54+36+6+5 = 1*3^2*6+2*3^1*6+1*3^0*6+5, so that parts have value 1, 2, 1, 5.

Is that the right decoding?

Bob

On Jan 1, 2019, at 11:05 PM, Alain LM <@AlanUS> wrote:

Hi All,

Doehler & Haass are using a ternary coding for CV 145-152 (Conditions for outputs) in order to pack 4 independent values with respectively 3, 3, 3 and 6 possible values each. Using the traditional binary coding would have required 9 bits (!) with some intermediate values wasted.

In order to split the trits (ternary bits...) and display each parameter individually, it would be required to expand the 'mask' principle by creating a new qualifier - for example base="3" or base="ternary".

I don't expect this to be overly complex, however as I'm not familiar with the symbolic programming Java code, I would highly appreciate if someone could:
- either provide me with guidance which files I need to look into to implement the change,
- or implement the change.

Also I was wondering if there is a need to expand the principle to other base value such as 5 (Quinary or pental).
For base 7, I don't see much interest (not enough 7-bits in a Byte...). Other lower values are multiple of 2 or 3, so the existing mask system will be enough.

--
Alain LM
--
Bob Jacobsen
@BobJacobsen

Alain LM
 

You look at CV145, and see a value of 101. This is 54+36+6+5 = 1*3^2*6+2*3^1*6+1*3^0*6+5, so that parts have value 1, 2, 1, 5.
Not quite. In base 3, 101 (decimal) would read 10202 (ternary), i.e. 1*3^4 + 0*3^3 +2*3^2 + 0*3^1 +2*3^0, or 81 + 18 + 0 + 2, so the parts would be 3, 2, 0, 2 with the masks being XVVXXX, XXXVXX, XXXXVX, XXXXXV.
The last setting is coded on two trits.
In this representation, I have used a mask with 6 trits, because the max value 255 (decimal) reads 100110 in ternary. Obviously not all values will be possible.
--
Alain LM

Bob Jacobsen
 

I’m confused.

The original post referred to "respectively 3, 3, 3 and 6 possible values each.” So how is that last 6 coded? As two sets of three somehow?

Let’s assume it lives in the LSB part of the work. Would the last choice (which I’ll call 5) be stored as binary bits 0101 or something else?

What number would be in the CZ for a 5 in the left most value and a 1 in the 2nd-from-left?

Bob

On Jan 2, 2019, at 3:30 PM, Alain LM <@AlanUS> wrote:

You look at CV145, and see a value of 101. This is 54+36+6+5 = 1*3^2*6+2*3^1*6+1*3^0*6+5, so that parts have value 1, 2, 1, 5.
Not quite. In base 3, 101 (decimal) would read 10202 (ternary), i.e. 1*3^4 + 0*3^3 +2*3^2 + 0*3^1 +2*3^0, or 81 + 18 + 0 + 2, so the parts would be 3, 2, 0, 2 with the masks being XVVXXX, XXXVXX, XXXXVX, XXXXXV.
The last setting is coded on two trits.
In this representation, I have used a mask with 6 trits, because the max value 255 (decimal) reads 100110 in ternary. Obviously not all values will be possible.
--
Alain LM
--
Bob Jacobsen
@BobJacobsen

Alain LM
 

Let’s assume it lives in the LSB part of the work
I'm afraid that you cannot think for LSB and MSB in this case, as these notions are for binary representation of a Byte. In the present case, D&H have used a ternary (base-3) representation, expressed in decimal values (in the documentation), to fit into a Byte that is by nature a binary representation.
So really an intellectual construction unrelated to the computer storage structure (made of bits, with all the bit operations that we know).

The original post referred to "respectively 3, 3, 3 and 6 possible values each.” So how is that last 6 coded? As two sets of three somehow?
Looking back at the D&H description of CV145: the confusion comes from the fact that there are 4 groups of parameters with, from top to bottom, respectively 2, 2, 2 and 5 values indicated. What is omitted is that each of these parameters can be disabled with value 0, hence in reality 3, 3, 3 and 6 options.
In ternary, each 'ternary bit' (or trit) can take the following values: 0, 1, 2.
For the last parameter that has 6 options, yes it requires 2 'trits', knowing that the whole range (9 values) is not used. So:
0 -->  000000 (ternary)
27 --> 001000 (ternary)
54 --> 002000 (ternary)
81 --> 010000 (ternary)
108 --> 011000 (ternary)
135 --> 012000 (ternary)

Now if you isolate (mask) trits #3 and #4 (starting with #0 on the right hand side) on the above, you get:
00 (ternary) --> 0 (decimal)
01 (ternary) --> 1 (decimal)
02 (ternary) --> 2 (decimal)
10 (ternary) --> 3 (decimal)
11 (ternary) --> 4 (decimal)
12 (ternary) --> 5 (decimal)

So in order to use the same principle as today for (binary) mask in JMRI, we will need to have 'trit' manipulation operators (masking, shifting). It also means that we cannot just directly manipulate bits of the CV, but first need to have a ternary representation of the CV, apply the changes using ternary operations, and then convert back this representation into a decimal for returning a new value to the CV.

I have no idea is such operators already exist in Java (or if a dedicated library exists).
--
Alain LM

RadSolution
 

I think some confusion could creep in here by use of the word 'ternary'.
A true ternary digit would be able to have 3 values, just as a binary digit ("bit") has 2 values (and a 'normal' digit has 10 values, 0-9).

What you are describing is a way of using a combination of several binary bits to hold a range of values, so more like octal encoding which uses 3 bits to hold one of 8 possible values.

I don't know if other groups of bits have names, apart from 1 = bit, 3 = octal and 4 = hexadecimal.
Perhaps 2 bits should be called tetra?
Perhaps 5 bits should be called penta?
Six bits becomes a problem; it should (logically) be hex, but 'hex' is almost universally (and incorrectly?) used a shorthand for hexadecimal...

Dave R

Alain LM
 

I don't know if other groups of bits have names
Base 3: Ternary
Base 4: Quaternary
Base 5: Quinary or pental
Base 6: Senary or Heximal
etc.
Full list here.

I'm not willing to bring confusion, but trying to use the proper terms for the underlying mathematical concept. In short, here we are trying to expand the concepts that all computer people know with binary, octal and hexadecimal to other base systems, notably bit manipulations.

--
Alain LM

Alain LM
 

What you are describing is a way of using a combination of several binary bits to hold a range of values, so more like octal encoding which uses 3 bits to hold one of 8 possible values.
The confusion holds to the fact that you are still think binary and its multiples. What I'm saying here, is that D&H have used an abstraction in base 3, where a 'ternary bit' (called a trit) has 3 values (0, 1, 2). This abstract representation has nothing to do with the way it will in the end be coded on a Byte.
--
Alain LM

RadSolution
 

Alain,

I understand that D&H are being 'abstract', but the fact remains that we are working with binary-based bytes in our computers.

So it isn't ternary, but binary-coded-ternary we would be using.
As there really isn't any such thing, we would be using 3/4 of the available values in a binary-coded-quatenary, with the last possible value unused.
Whatever we do, we must use an integer number of bits, so will always have a multiple of 2 values available, even if we don't want them all....

Dave

Balazs Racz
 

I'm wondering if instead of implementing special encodings for all the different flavours decoder manufacturers can come up with, we might be better off with an expression based solution that would be able to cover all these weird cases. This way supporting special encodings can be done purely by XML changes instead of java changes.

I think we can describe one such custom encoded field with the following parameters:
- CV number which to refer to in the decoder
- minimum and maximum value
- a mathematical expression that, given the CV value, gives the current value of the field (aka "getter")
- a mathematical expression that, given the current CV value and the new field value, computes what the new CV value should be with the field overwritten (aka "setter").

As a simple example let's take a nibble coded CV. 
Field1 (low nibble):
- min = 0, max = 15
- getter is "$cv & 15"
- setter is "($cv & 0xF0) + ($field & 0xF)"

Field2 (high nibble):
- min = 0, max = 15
- getter is "($cv / 16) & 15"
- setter is "($cv & 0x0F) + ($field * 16)"

The same thing works for the "decimal coded" stuff:
Field1 (unit in decimal)
- min = 0, max = 9
- getter is "$cv % 10"
- setter is "($cv / 10) * 10 + ($field % 10)"

Field2 (tens in decimal)
- min = 0, max = 9
- getter is "($cv / 10) % 10"
- setter is "($cv / 100) * 100 + ($cv % 10) + ($field % 10) * 10"

Field3 (hundreds in decimal)
- min = 0, max = 1
- getter is "($cv / 100)"
- setter is "($cv % 100) + ($field) * 100"

The trick is that instead of defining how a single CV is decomposed into N values (which would need a variable number of parameters) we only need to define the relation of one field to the CV, so the number of parameters is fixed. We repeat instead the field definition, so we can have a CV with 2 fields in it, 3, 4, etc.
Ternary encodings would also work and even a mixed encoding where some 3-way fields are trits and there is a "two-trit" field with 0..8 as values would also be fine.

Of course the java code will be more effort, especially ugly to write unless we can find an existing library for expression evaluation that would eat something like the above syntax. But it could end the story of new encodings popping up and causing trouble.

WDYT?

Balazs



Alain LM
 

On Thu, Jan 3, 2019 at 01:36 PM, RadSolution wrote:
So it isn't ternary, but binary-coded-ternary we would be using.
As there really isn't any such thing, we would be using 3/4 of the available values in a binary-coded-quatenary, with the last possible value unused.
Yes of course 'binary-coded-ternary', and even 'decimal-coded-ternary' given the way this is presented in D&H documentation (very confusing actually)
And yes again, the abstract representation does not use the full span of a 6-trit number, as we only have a Byte with 255 (decimal) as maximal value i.e. 100110 (ternary).
 
--
Alain LM

Alain LM
 

On Thu, Jan 3, 2019 at 01:53 PM, Balazs Racz wrote:
we might be better off with an expression based solution that would be able to cover all these weird cases
Could be interesting, as there are some other weird cases that I have in mind. On the other hand, more complex to understand for the decoder definition developers who are not necessarily familiar with such expressions, mixing modulo, integer division and bit array operators.
 
--
Alain LM

Bob Jacobsen
 

On Jan 3, 2019, at 12:14 AM, Alain LM <@AlanUS> wrote:

Let’s assume it lives in the LSB part of the work
I'm afraid that you cannot think for LSB and MSB in this case, as these notions are for binary representation of a Byte. In the present case, D&H have used a ternary (base-3) representation, expressed in decimal values (in the documentation), to fit into a Byte that is by nature a binary representation.
So really an intellectual construction unrelated to the computer storage structure (made of bits, with all the bit operations that we know).
I’m sorry, but I’m not smart enough to understand the above. In the end, this _must_ be stored in a CV which is a set of binary bits. I’m trying to understand how to map these values to those bits.

The original post referred to "respectively 3, 3, 3 and 6 possible values each.” So how is that last 6 coded? As two sets of three somehow?
Looking back at the D&H description of CV145: the confusion comes from the fact that there are 4 groups of parameters with, from top to bottom, respectively 2, 2, 2 and 5 values indicated. What is omitted is that each of these parameters can be disabled with value 0, hence in reality 3, 3, 3 and 6 options.
In ternary, each 'ternary bit' (or trit) can take the following values: 0, 1, 2.
For the last parameter that has 6 options, yes it requires 2 'trits', knowing that the whole range (9 values) is not used. So:
0 --> 000000 (ternary)
27 --> 001000 (ternary)
54 --> 002000 (ternary)
81 --> 010000 (ternary)
108 --> 011000 (ternary)
135 --> 012000 (ternary)

Now if you isolate (mask) trits #3 and #4 (starting with #0 on the right hand side) on the above, you get:
00 (ternary) --> 0 (decimal)
01 (ternary) --> 1 (decimal)
02 (ternary) --> 2 (decimal)
10 (ternary) --> 3 (decimal)
11 (ternary) --> 4 (decimal)
12 (ternary) --> 5 (decimal)

So in order to use the same principle as today for (binary) mask in JMRI, we will need to have 'trit' manipulation operators (masking, shifting). It also means that we cannot just directly manipulate bits of the CV, but first need to have a ternary representation of the CV, apply the changes using ternary operations, and then convert back this representation into a decimal for returning a new value to the CV.

I have no idea is such operators already exist in Java (or if a dedicated library exists).
I’m not sure which has a max value of 5 or 2, so let’s skip questions of which end of the byte, so let me ask in a simpler form:

For each of those four parameters, what’s stored in the CV when it has its highest possible value and all the others are zero?

Specifically:
when the parameter that goes to 5 has a value 5, what is stored in the CV?
ditto for a value 2 in each of the other parameters, what’s stored?

Bob

--
Bob Jacobsen
@BobJacobsen

Bob Jacobsen
 

That’s why I want those sample variables. I don’t think the computation needs to be anything complicated. If the values really are coded 1,2,3,4,5, etc all you need is “how is a 1 coded in this variable?” and “what’s the maximum value for this variable?”.

Then you divide the CV value into (all int computation)

partA = CVvalue%oneCoding
partB = CVvalue/onecodeing%maxValue
partC = CVvalue%(oneCoding*(maxValue+1))

update/use partB as needed, and then reassemble after modifying partB as desired.

But all this discussion of trinary, failnary, etc has confused me as to how the values >2 are coded.

Bob

--
Bob Jacobsen
@BobJacobsen

Alain LM
 

As mentioned in the previous post, I've attached a simple Excel sheet that illustrates the above. Note that the base number can be changed so you have a free converter to other bases than 3; to illustrate the notion of 'base-n bit' whatever they are called...
I hope this helps.
Obviously the formulas in Excel are not very subtle. In a programmatic way, all this is very easy to do with a simple recursive function.
--
Alain LM

Alain LM
 

Better version of the Excel sheet
--
Alain LM

Alain LM
 

On Thu, Jan 3, 2019 at 08:51 PM, Bob Jacobsen wrote:
For each of those four parameters, what’s stored in the CV when it has its highest possible value and all the others are zero?

Specifically:
when the parameter that goes to 5 has a value 5, what is stored in the CV?
ditto for a value 2 in each of the other parameters, what’s stored?
From top to bottom (as displayed on D&H manual):
- 1st parameter: values 1 and 2 (max) , i.e. 1*3^0 and 2*3^0   (trit 0)
- 2nd parameter: values 3 and 6 (max) , i.e. 1*3^1 and 2*3^1   (trit 1)
- 3rd parameter: values 9 and 18 (max) , i.e. 1*3^2 and 2*3^2  (trit 2)
- 4th parameter: values 27, 54, 81, 108 and 135 (max), i.e. 0*3^4 + 1*3^3, 0*3^4 + 2*3^3, 1*3^4 + 0*3^3, 1*3^4 + 1*3^3 and 1*3^4 + 2*3^3 (trits 3 and 4), i.e. ternary values of 01, 02, 10, 11 and 12 over the two trits, i.e. 1, 2, 3, 4 and 5 in decimal.
Also remember that value 0 is possible for all 4 parameters (meaning feature deactivated).

Obviously the global value is stored in a byte, so the above is an abstract representation. In practice what is needed is convert the decimal value in the byte in a ternary (base 3) representation, do the manipulations based on trit (base-3 'bits'), and then convert back in decimal.
In binary we would use the usual bit manipulation operators (shift, OR, XOR, AND) to change only one or some selected bits in a byte. Here we will need to write some adhoc functions to do the same.The number converted in base-3 could be seen as an array of integers with each member of the array having only 3 possible values 0, 1 and 2; from there it would be easy to substitute only one or several of array members (trits...).
I will write a small XLS sheet to explain this hopefully better (through I've been trying already).
 
--
Alain LM

Bob Jacobsen
 

I’ve now got code in my bobjacobsen/dp-var-base-update branch (available on GitHub) that will handle these cases, I think.

It works by (optionally) putting a decimal radix value in the mask field, instead of a bit-based mask.

For example, to define two variables to represent a CV that holds two decimal values: (note this is _NOT_ two BCD digits, which remains unsupported except via the “two combined variables” hack):
*) define the first with max=“9” and mask=“10”
*) define the second with max=“9” and mask=“1”

I think the D&H example would be variables:

*) One with max=“2” and mask=“1”
*) One with max=“2” and mask=“3”
*) One with max=“2” and mask=“9”
*) One with max=“5” and mask=27”

but I’m not certain of that last.

Would appreciate heading if this works.

Bob

--
Bob Jacobsen
@BobJacobsen

Alain LM
 

On Fri, Jan 4, 2019 at 06:10 PM, Bob Jacobsen wrote:
It works by (optionally) putting a decimal radix value in the mask field, instead of a bit-based mask.

For example, to define two variables to represent a CV that holds two decimal values: (note this is _NOT_ two BCD digits, which remains unsupported except via the “two combined variables” hack):
*) define the first with max=“9” and mask=“10”
*) define the second with max=“9” and mask=“1”
For clarification:
max="x" is the existing qualifier for <decVal/>?
mask="y" is a new possible form for the existing qualifier of <variable/>

Right?
 
--
Alain LM

Bob Jacobsen
 

Not sure what’s meant by x and y.

This element should work:

<variable item=“Three-State Thing" CV=“9” mask=“9">
<decVal max=“2"/>
</variable>

Note that the maximum value of a 3-state thing is 2, with the states being 0, 1, 2.

So the mask attribute can be either a bit-mask definition like XXXVVVXX, or it can represent the numerical base for storing the 0…max values. It’s up to the person writing the files to make sure that (inadvertently) overlapping values are not defined, just like it is with the existing bit-mask form.

All the various include/exclude logic, read/write prioritization, etc should still work. It’s just a different way of defining the packing in the CV byte.

I think the enum form is also working, but haven’t written enough tests yet. SplitVal is definitely _not_ working yet.

Bob


On Jan 4, 2019, at 11:37 AM, Alain LM <@AlanUS> wrote:

On Fri, Jan 4, 2019 at 06:10 PM, Bob Jacobsen wrote:
It works by (optionally) putting a decimal radix value in the mask field, instead of a bit-based mask.

For example, to define two variables to represent a CV that holds two decimal values: (note this is _NOT_ two BCD digits, which remains unsupported except via the “two combined variables” hack):
*) define the first with max=“9” and mask=“10”
*) define the second with max=“9” and mask=“1”
For clarification:
max="x" is the existing qualifier for <decVal/>?
mask="y" is a new possible form for the existing qualifier of <variable/>

Right?

--
Alain LM
--
Bob Jacobsen
@BobJacobsen