Ripple carry
You will learn
How a row of full adders adds two numbers, the carry walking left.
Line up full adders, one per place, and feed each carry into the next: a ripple-carry adder. 13 + 1 opens the widget: the ones place makes 2 = 3 - 1, so a carry of +1 walks through three places and +++ becomes +---. The spec's ripple_add() is checked against plain addition on 198 pairs. The lesson spec builds a 2-bit binary ripple adder from the same ternary parts.
Try it
Press play and stop at the column where the carry first turns back to 0; then try 40 + 41.
Two numbers, one full adder per place, the carry walking left. Press play to watch every column decide its sum.
specs/ternary/ternary_ripple_adder.t27
module TernaryRippleAdder;
// Binary bits are embedded as trits: 0 -> N(0b00), 1 -> P(0b10). All logic is
// the spec-first ternary stack; add2 is a 2-bit ripple-carry adder = two full
// adders with the carry threaded between them.
fn tmul(ta: u8, tb: u8) -> i8 {
if (ta == 1) { return 0; }
if (tb == 1) { return 0; }
if (ta == tb) { return 1; }
return -1;
}
fn dot27(a: u64, b: u64) -> i16 {
var acc : i16 = 0;
var i : u32 = 0;
while (i < 27) {
var ta : u8 = ((a >> (i << 1)) & 3) as u8;
var tb : u8 = ((b >> (i << 1)) & 3) as u8;
acc = acc + tmul(ta, tb) as i16;
i = i + 1;
}
return acc;
}
fn sign0(v: i16) -> u8 { if (v > 0) { return 2; } if (v < 0) { return 0; } return 1; }
fn negate(t: u8) -> u8 { if (t == 2) { return 0; } if (t == 0) { return 2; } return 1; }
fn pack2(t0: u8, t1: u8) -> u64 {
var z : u64 = 6004799503160661;
var cleared : u64 = z & 18446744073709551600;
return cleared | (t0 as u64) | ((t1 as u64) << 2);
}
fn pack3(t0: u8, t1: u8, t2: u8) -> u64 {
var z : u64 = 6004799503160661;
var cleared : u64 = z & 18446744073709551552;
return cleared | (t0 as u64) | ((t1 as u64) << 2) | ((t2 as u64) << 4);
}
fn bneuron(x: u64, w: u64, bias: i16) -> u8 { return sign0(dot27(x, w) + bias); }
fn xor2(a: u8, b: u8) -> u8 {
var x : u64 = pack2(a, b);
var w : u64 = pack2(2, 2);
var h1 : u8 = bneuron(x, w, -1);
var h2 : u8 = bneuron(x, w, 1);
return bneuron(pack2(h2, negate(h1)), w, -1);
}
fn maj3(a: u8, b: u8, c: u8) -> u8 { return sign0(dot27(pack3(a, b, c), 12009599006321322)); }
// One full adder: returns the sum trit in bits[1:0] and the carry trit in [3:2].
fn full_adder(a: u8, b: u8, cin: u8) -> u8 {
var s : u8 = xor2(xor2(a, b), cin);
var carry : u8 = maj3(a, b, cin);
return (carry << 2) | s;
}
// 2-bit ripple-carry adder: a = {a1,a0}, b = {b1,b0} (LSB first), each bit a
// trit-embedded binary. Threads carry0 -> full adder 1. Returns 3 result trits
// packed: sum0 in [1:0], sum1 in [3:2], carry-out in [5:4].
pub fn add2(a0: u8, a1: u8, b0: u8, b1: u8) -> u8 {
var fa0 : u8 = full_adder(a0, b0, 0);
var s0 : u8 = (fa0 & 3) as u8;
var c0 : u8 = ((fa0 >> 2) & 3) as u8;
var fa1 : u8 = full_adder(a1, b1, c0);
var s1 : u8 = (fa1 & 3) as u8;
var c1 : u8 = ((fa1 >> 2) & 3) as u8;
return (s0 as u64 | ((s1 as u64) << 2) | ((c1 as u64) << 4)) as u8;
}
// 0 + 0 = 00, carry 0 -> s0=N,s1=N,c=N -> 0
test add_0_0 { assert_eq(add2(0, 0, 0, 0), 0); }
// 1 + 1 = 10 (a=01,b=01): s0=N(0), s1=P(1), c=N -> (0)|(2<<2)|(0<<4)=8
test add_1_1 { assert_eq(add2(2, 0, 2, 0), 8); }
// 3 + 1 = 100 (a=11,b=01): s0=N, s1=N, c=P -> (0)|(0<<2)|(2<<4)=32
test add_3_1 { assert_eq(add2(2, 2, 2, 0), 32); }
// 3 + 3 = 110 (a=11,b=11): s0=N, s1=P, c=P -> 0|(2<<2)|(2<<4)=8|32=40
test add_3_3 { assert_eq(add2(2, 2, 2, 2), 40); }
// 2 + 1 = 011 (a=10,b=01): a0=N,a1=P,b0=P,b1=N -> s0=P, s1=P, c=N -> 2|(2<<2)|0=10
test add_2_1 { assert_eq(add2(0, 2, 2, 0), 10); }
// W697: the hardware boundary, derived from the CALL GRAPH.
//
// This spec has several functions that take a parameter and return a value,
// so W696's count rule left it AMBIGUOUS. But exactly ONE of them is called
// by no other function -- it is the root, and every other candidate is a
// helper it reaches. With one root the choice is forced by structure rather
// than by count, and forwarding to it still invents nothing.
//
// The call graph is built from FUNCTION BODIES ONLY. Counting `test` blocks
// as callers makes the rule vacuous -- every function is called by its own
// test, so nothing is ever a root.
//
// Measured: the rule resolved 14 of 136 ambiguous specs, 6 of them with
// types that can cross a module boundary. It is narrow because most of the
// rest are libraries of INDEPENDENT functions, which have several roots and
// correctly stay ambiguous.
fn on_comb(a0: u8, a1: u8, b0: u8, b1: u8) -> u8 { return add2(a0, a1, b0, b1); }
endmodule
All lessons
Module 1 · Three values
Why three, how balanced ternary writes every number without a sign, and what flipping and cutting trits do.
Module 2 · Logic with unknown
Kleene's three-valued gates, two gates binary has no twin for, and addition as a pair of tables.
Module 3 · Adding trits
The half adder, the full adder and a carry that ripples left, one place at a time.
Module 4 · Multiplying without a multiplier
Copy, drop or flip: a product by one trit, long multiplication, and a MAC that only adds.
Module 5 · Trits in binary memory
Two bits per trit, five trits per byte, and the bits a 27-trit word needs.
Module 6 · The TRI-27 instruction word
The 32-bit word the Trinity emulator decodes: its fields, its 47 opcodes and its 15-bit immediate.
Module 7 · A ternary machine
An ALU built from this course's adders, a three-way jump, and a program you can step.
Module 8 · Three answers
Compare at the highest differing trit, find a number in thirds, sort with three-way compares.
Module 9 · Ternary neurons
Weights of -1, 0, +1: one neuron, a detector and a small layer, with no multiplier anywhere.