Lesson 5. The chaos game: a triangle from chance

After this lesson the same Sierpinski triangle grows out of random dots on a second screen. The circuit rolls a "die", steps half-way to the vertex it picked and puts a dot — and not a single dot lands off the triangle.

5.1. The idea: a half-way step

Take the three vertices of a triangle and any dot. Roll a die: it picks a vertex — step half-way to it and put a dot. Repeat. You would think the dots land anywhere — but they form the Sierpinski triangle.

The chaos game: a step half-way to a random vertex. After a few steps the dot can no longer leave the Sierpinski triangle, and random dots paint all of it.

5.2. The idea: a step is a shift

A half-way step is (x + v) / 2, which would need an adder. But if the vertices are at (0, 0), (64, 0) and (0, 64), then (x + 64) / 2 and x / 2 are just a shift right, with the vertex bit pushed in at the top: 1 — towards 64, 0 — towards zero.

A step half-way to the vertex 64 is a shift right with a 1 pushed in at the top; towards the vertex 0 a 0 is pushed in. So the coordinate is a shift register — no adder needed.

A 1 is never pushed into x and y at once — so the dot has no common 1 bit: exactly the lesson 4 rule (x AND y) = 0.

Where chance comes from. An LFSR is a shift register that feeds itself: the new bit is the XOR of a few of its bits. 12 bits run through all 4095 non-zero values in a "random" order. Fewer will not do: a dot depends on the last six rolls, and a short generator will not produce all their combinations — the triangle will not fill.

5.3. Building

The same project: the scan and the lesson 4 triangle stay, a second screen goes next to them.

The game. Take the three vertices of a triangle and any dot. Roll a die: it picks a vertex — step half-way to it and put a dot. Repeat. You would think the dots land anywhere — but they form the Sierpinski triangle.

How it works in hardware. A half-way step is (x + v) / 2, which would need an adder. But if the vertices are at (0, 0), (64, 0) and (0, 64), then (x + 64) / 2 and x / 2 are just a shift right with the vertex bit pushed in at the top: 1 — towards 64, 0 — towards zero. The coordinate is a shift register, no adder needed.

a	b	Vertex	Pushed in: x	y
1	0	(64, 0)	1	0
0	1	(0, 64)	0	1
0	0	(0, 0)	0	0
1	1	(0, 0)	0	0

A 1 is never pushed into x and y at once — so the dot has no common 1 bit: exactly the lesson 4 rule (x AND y) = 0. The same triangle — from logic on the left and from chance on the right.

Where chance comes from. An LFSR is a shift register that feeds itself: the new bit is the XOR of a few of its bits. It runs through all 4095 non-zero values in a "random" order. Fewer than 12 bits will not do: a dot depends on the last six rolls, and a short generator will not produce all their combinations — the triangle will not fill.

Step 1. LFSR12 — the random bit generator

Part	Pin	Label
Input port	out	CLK
Input port	out	RST
NOT	I0 O0	RST nRST
XOR	I0 I1 O0	r11 r5 f1
XOR	I0 I1 O0	f1 r3 f2
XOR (feedback)	I0 I1 O0	f2 r0 fb
AND	I0 I1 O0	fb nRST g0
OR (reset to 1)	I0 I1 O0	g0 RST d0
DFF (bit 0)	D CLK Q nQ	d0 CLK r0 — (free)
AND (bit 1)	I0 I1 O0	r0 nRST d1
DFF (bit 1)	D CLK Q nQ	d1 CLK r1 — (free)
AND (bit 2)	I0 I1 O0	r1 nRST d2
DFF (bit 2)	D CLK Q nQ	d2 CLK r2 — (free)
AND (bit 3)	I0 I1 O0	r2 nRST d3
DFF (bit 3)	D CLK Q nQ	d3 CLK r3 — (free)
AND (bit 4)	I0 I1 O0	r3 nRST d4
DFF (bit 4)	D CLK Q nQ	d4 CLK r4 — (free)
AND (bit 5)	I0 I1 O0	r4 nRST d5
DFF (bit 5)	D CLK Q nQ	d5 CLK r5 — (free)
AND (bit 6)	I0 I1 O0	r5 nRST d6
DFF (bit 6)	D CLK Q nQ	d6 CLK r6 — (free)
AND (bit 7)	I0 I1 O0	r6 nRST d7
DFF (bit 7)	D CLK Q nQ	d7 CLK r7 — (free)
AND (bit 8)	I0 I1 O0	r7 nRST d8
DFF (bit 8)	D CLK Q nQ	d8 CLK r8 — (free)
AND (bit 9)	I0 I1 O0	r8 nRST d9
DFF (bit 9)	D CLK Q nQ	d9 CLK r9 — (free)
AND (bit 10)	I0 I1 O0	r9 nRST d10
DFF (bit 10)	D CLK Q nQ	d10 CLK r10 — (free)
AND (bit 11)	I0 I1 O0	r10 nRST d11
DFF (bit 11)	D CLK Q nQ	d11 CLK r11 — (free)
OR (output A)	I0 I1 O0	r0 r0 A
OR (output B)	I0 I1 O0	r6 r6 B
Output port	in	A
Output port	in	B

Ctrl+G → name LFSR12. Pins: inputs CLK, RST; outputs A (bit 0), B (bit 6). An OR with both inputs the same is just a "wire" from the inner label to the port.

Step 2. SHIFT6 — the coordinate shift register

Part	Pin	Label
Input port	out	CLK
Input port	out	RST
Input port	out	IN
NOT	I0 O0	RST nRST
AND (bit 5)	I0 I1 O0	IN nRST d5
DFF (bit 5)	D CLK Q nQ	d5 CLK Q5 — (free)
AND (bit 4)	I0 I1 O0	Q5 nRST d4
DFF (bit 4)	D CLK Q nQ	d4 CLK Q4 — (free)
AND (bit 3)	I0 I1 O0	Q4 nRST d3
DFF (bit 3)	D CLK Q nQ	d3 CLK Q3 — (free)
AND (bit 2)	I0 I1 O0	Q3 nRST d2
DFF (bit 2)	D CLK Q nQ	d2 CLK Q2 — (free)
AND (bit 1)	I0 I1 O0	Q2 nRST d1
DFF (bit 1)	D CLK Q nQ	d1 CLK Q1 — (free)
AND (bit 0)	I0 I1 O0	Q1 nRST d0
DFF (bit 0)	D CLK Q nQ	d0 CLK Q0 — (free)
Output port	in	Q0
Output port	in	Q1
Output port	in	Q2
Output port	in	Q3
Output port	in	Q4
Output port	in	Q5

Ctrl+G → name SHIFT6. Pins: inputs CLK, RST, IN; outputs Q0–Q5.

Step 3. Canvas: chance, vertex, coordinates, second screen

Part	Pin	Label
LFSR12	CLK RST A B	CLK RST ra rb
NOT	I0 O0	ra nra
NOT	I0 O0	rb nrb
AND (vertex x)	I0 I1 O0	ra nrb kx
AND (vertex y)	I0 I1 O0	rb nra ky
SHIFT6 (coordinate x)	CLK RST IN Q0 Q1 Q2 Q3 Q4 Q5	CLK RST kx px0 px1 px2 px3 px4 px5
SHIFT6 (coordinate y)	CLK RST IN Q0 Q1 Q2 Q3 Q4 Q5	CLK RST ky py0 py1 py2 py3 py4 py5
Dot display (second)	X0 X1 X2 X3 X4 X5 Y0 Y1 Y2 Y3 Y4 Y5 D0 WE CLK CLR	px0 px1 px2 px3 px4 px5 py0 py1 py2 py3 py4 py5 VCC VCC nCLK GND

CLK, nCLK and RST are the same labels as the lesson 3 scan.

5.4. Check

№	What to do	What you see
1	second screen — same settings as the first (Dots, 64 × 64, 1 dot)	—
2	RST = 1, one clock, RST = 0; clock at 60Hz	dots appear on the second screen one by one, in random places
3	look closely: not a single dot landed "off"	each one is on the triangle, even though the place was chosen at random
4	clock at 4kHz or faster, wait a couple of seconds	the second screen is filled — the same triangle as on the first

If dots land outside the triangle, check the vertices: AND (vertex x) has nrb on its second input, AND (vertex y) has nra. If the second screen does not fill completely, check the LFSR12 feedback bits: r11, r5, r3, r0.

Lesson 5 paste (`Cmd+I`)

Needs NOT, AND, OR, XOR, DFF; the labels CLK, nCLK, RST come from lesson 3.

# Lesson 5 — the chaos game: random vertex, half-way step as a shift, second screen.chip LFSR12 {  portIn(CLK)  portIn(RST)  portOut(A)  portOut(B)  NOT(RST, nRST)  XOR(r11, r5, f1)  XOR(f1, r3, f2)  XOR(f2, r0, fb)  AND(fb, nRST, g0)  OR(g0, RST, d0)  DFF(D=d0, CLK=CLK, Q=r0)  AND(r0, nRST, d1)  DFF(D=d1, CLK=CLK, Q=r1)  AND(r1, nRST, d2)  DFF(D=d2, CLK=CLK, Q=r2)  AND(r2, nRST, d3)  DFF(D=d3, CLK=CLK, Q=r3)  AND(r3, nRST, d4)  DFF(D=d4, CLK=CLK, Q=r4)  AND(r4, nRST, d5)  DFF(D=d5, CLK=CLK, Q=r5)  AND(r5, nRST, d6)  DFF(D=d6, CLK=CLK, Q=r6)  AND(r6, nRST, d7)  DFF(D=d7, CLK=CLK, Q=r7)  AND(r7, nRST, d8)  DFF(D=d8, CLK=CLK, Q=r8)  AND(r8, nRST, d9)  DFF(D=d9, CLK=CLK, Q=r9)  AND(r9, nRST, d10)  DFF(D=d10, CLK=CLK, Q=r10)  AND(r10, nRST, d11)  DFF(D=d11, CLK=CLK, Q=r11)  OR(r0, r0, A)  OR(r6, r6, B)} chip SHIFT6 {  portIn(CLK)  portIn(RST)  portIn(IN)  portOut(Q0)  portOut(Q1)  portOut(Q2)  portOut(Q3)  portOut(Q4)  portOut(Q5)  NOT(RST, nRST)  AND(IN, nRST, d5)  DFF(D=d5, CLK=CLK, Q=Q5)  AND(Q5, nRST, d4)  DFF(D=d4, CLK=CLK, Q=Q4)  AND(Q4, nRST, d3)  DFF(D=d3, CLK=CLK, Q=Q3)  AND(Q3, nRST, d2)  DFF(D=d2, CLK=CLK, Q=Q2)  AND(Q2, nRST, d1)  DFF(D=d1, CLK=CLK, Q=Q1)  AND(Q1, nRST, d0)  DFF(D=d0, CLK=CLK, Q=Q0)} LFSR12(CLK=CLK, RST=RST, A=ra, B=rb)NOT(ra, nra)NOT(rb, nrb)AND(ra, nrb, kx)AND(rb, nra, ky)SHIFT6(CLK=CLK, RST=RST, IN=kx, Q0=px0, Q1=px1, Q2=px2, Q3=px3, Q4=px4, Q5=px5)SHIFT6(CLK=CLK, RST=RST, IN=ky, Q0=py0, Q1=py1, Q2=py2, Q3=py3, Q4=py4, Q5=py5)dotdisplay SCR2{layout=dots, w=64, h=64}(X0=px0, X1=px1, X2=px2, X3=px3, X4=px4, X5=px5, Y0=py0, Y1=py1, Y2=py2, Y3=py3, Y4=py4, Y5=py5, D0=VCC, WE=VCC, CLK=nCLK, CLR=GND)

¿No te sale? Algo no funciona →