Module fe17_kara 

The 150-DSP field multiplier: three-way subtractive Karatsuba.

FieldMulKara is a drop-in for FieldMulPar: the same ports, the same initiation interval of one and the same MUL_LATENCY, with 150 DSPs instead of 225.

The split

The fifteen 17-bit digits of each factor form three blocks of five, A = A0 + A1 X + A2 X^2 with X = 2^85. Schoolbook needs nine block products; Karatsuba needs six, all of five by five digits:

• P00 = A0 B0, P11 = A1 B1, P22 = A2 B2;
• D01 = (A0 - A1)(B0 - B1), D02 = (A0 - A2)(B0 - B2), D12 = (A1 - A2)(B1 - B2), digit by digit.

The coefficients of X^u are then G0 = P00, G1 = P00 + P11 - D01, G2 = P00 + P11 + P22 - D02, G3 = P11 + P22 - D12 and G4 = P22. The differences are digit-wise, so each difference digit is within ±(2^17 - 1): an 18-bit signed operand, which is exactly what a DSP48E2’s 18-bit port takes, and each product (18 x 18 signed) is one DSP. Six block products of 25 digit products are the 150 DSPs.

Pipeline

Edge	Step
1	capture a, b
2	form the six operand rows (the differences are fabric subtracts)
3..7	five multiply-accumulate stages (KaraStage); stage s adds x_s y_j to columns s + j
8	S = P00 + P11, T = P11 + P22
9	G1 = S - D01, G2' = S + P22, G3 = T - D12
10	G2 = G2' - D02
11	the 29 product columns C_t from the overlapping G_u
12	fold: c_k = C_k + 19 C_{k+15} (2^255 = 19 mod p)
13..18	MulNorm, shared with the 225-DSP unit
19..23	result delay, so the latency matches the 225-DSP unit

Every true column C_t is a sum of digit products, so it is non-negative and below 15 (2^17 - 1)^2 < 2^38, whatever signs the intermediate Karatsuba terms take; the folded columns are below 2^43, the normalizer’s input width.

Structs

FieldMulKara

Initiation-interval-one, 150-DSP canonical field multiplier (see the module documentation).

KaraIo

What one KaraStage passes to the next, for all six block products.

KaraRow

Operand row of one block product: the multiplier digits still to use (this stage’s first) and the five multiplicand digits.

KaraStage

One multiply-accumulate stage of all six block products (30 DSPs).

Functions

digit_s18

A 17-bit digit as a non-negative 18-bit signed operand.

field_mul_kara_kernel

State transition for FieldMulKara.

kara_stage_kernel

State transition for KaraStage: win[j] += x[0] * y[j] (one DSP each, an exact 18 x 18 signed product), then retire column 0 and shift.

times19_col

19 x for a product column (16x + 2x + x).