网表格式
TapeOut 电路的网表是一列二输入 NAND 门:pairs 写每个门接哪两根线,taps 写输出取哪几根线。
字段
| 字段 | 类型 | 说明 |
|---|---|---|
pairs | [[a, b], …] | 按顺序的 NAND 门。pairs[i] = [a, b] 表示这个门的输出 = NAND(线 a, 线 b)。必填 |
taps | [int, …] | 第 o 个输出取哪根线。必填 |
nIn | int | 输入个数 |
nOut | int | 输出个数,等于 len(taps) |
g | int | 门数,等于 len(pairs) |
d | int | 深度:所有输出线里最大的深度 |
C | int | 代价 g · d³ |
srcId 或 id | int | 题号。不同文件用的键名不同,意思一样 |
last_outs | bool | 输出是不是正好是最后 nOut 个门 |
上链格式另有:
| 字段 | 说明 |
|---|---|
enc | "chain" |
n_base | 2 + nIn:常量 ZERO、ONE 加输入 |
nl_hex | 链上网表字节的十六进制,0x 开头 |
nl_len | nl_hex 解出来的字节数 |
线号
有两种排法,区别在常量。
输入从 0 起(设计工具输出常用):
| 线号 | 是什么 | 深度 |
|---|---|---|
0 … nIn−1 | 输入 in0 … in{nIn−1} | 0 |
nIn + i | 第 i 个门 | 1 + max(深度 a, 深度 b) |
上链格式(常量占 0、1):
| 线号 | 是什么 | 深度 |
|---|---|---|
0 | 常量 ZERO,不算门 | 0 |
1 | 常量 ONE,不算门 | 0 |
2 … nIn+1 | 输入 | 0 |
n_base + i | 第 i 个门,算进 g | 1 + max(深度 a, 深度 b) |
门
val[w] = 1 − (val[a] & val[b])- 只有一种门:二输入 NAND。
NAND(x, x) = NOT(x)。取反靠这个,没有单独的极性字段。- 门的两个输入只能引用已经有的线:输入、常量或更早的门。
- 两个输入的先后不影响结果,也不强制顺序。
深度和代价
- 输入和常量深度 0;门的深度 = 1 + 两个输入里较大的深度。
d= 所有输出线里最大的深度。C = g · d³。g不算常量 ZERO、ONE。
输出必须是最后几个门
上链格式要求 taps 正好是最后 nOut 个门:
base = nIn(输入从 0 起)或 n_base(上链格式)
taps == [base + g − nOut, …, base + g − 1],且 0 < nOut ≤ g不满足时要先转换:把输出门复制到末尾,再删掉没人用的门。转换可能多出门、变深,所以代价按转换之后的 g、d 算。
链上网表字节(nl_hex)
纯 NAND 网表每个门 7 字节:
| 偏移 | 长度 | 内容 |
|---|---|---|
| 0 | 1 | opcode,0 = NAND2 |
| 1 | 3 | 输入 a 的线号,大端 |
| 4 | 3 | 输入 b 的线号,大端 |
总长 = g × 7。线号是上链格式的。
真值表位序
in0是输入组合编号的最低位。- 官方向量的十六进制里,
in_k在第k // 8个字节的第k % 8位。
例子
一个 6 输入、3 输出的电路,两种格式各一份:
| 项 | 输入从 0 起 | 上链格式 |
|---|---|---|
nIn、nOut | 6、3 | 6、3 |
g、d | 47、8 | 47、8 |
C | 24,064 = 47 × 8³ | 同左 |
n_base | — | 8 |
| 前三个门 | [0,0]、[2,2]、[6,7] | [2,2]、[4,4]、[8,9] |
taps | [50, 51, 52] = 6 + 47 − 3 起 | [52, 53, 54] = 8 + 47 − 3 起 |
nl_len | — | 329 = 47 × 7 |
nl_hex 开头 | — | 0x00 000002 000002 …(第一个门 NAND(2, 2)) |
不合法的网表
len(taps) ≠ nOutg ≠ len(pairs)C ≠ g · d³- 门引用了后面才有的线(成环或未定义)
还没定的
- 链上 opcode 除了
0的完整表(时序电路用的 LATCH 等)。 - 显式的版本字段
schema_version、线号排法字段wire_base:只是提议,还没用。