Padding for Same Convolution

1. Background Knowledge

Convolution Operation: In CNNs, convolution slides a filter (kernel) of size $F \times F$ over input of size $I \times I$, computing dot products at each position. Without padding, output size shrinks.

Output Size Formula (stride $S=1$): $O = I - F + 2P + 1$ where $P$ is padding added equally to both sides.

Same Padding: Set $O = I$ to preserve dimensions: $I = I - F + 2P + 1$ $\Rightarrow 2P = F - 1$ $\Rightarrow P = \frac{F-1}{2}$ Odd $F$ ensures $P$ is integer (e.g., $F=5 \Rightarrow P=2$).

Why Padding Matters: Zero-padding enables translation equivariance (features shift predictably) and maintains size through network layers.

2. Algorithm Approach

Direct Mathematical Computation: Use the derived formula $P = \frac{F-1}{2}$. Since $F$ is guaranteed odd, no floating-point or rounding needed.

Integer Arithmetic: In Python, (F-1)//2 performs floor division, safe for odd positives.

No Search/Iteration Required: Purely algebraic—no loops, tables, or conditionals.

3. Step-by-Step Strategy

1. Input: Receive odd integer filter_size ($F$).
2. Compute: $P = \frac{F-1}{2}$.
3. Return: Integer $P$.

def calculate_same_padding(filter_size):
 return (filter_size - 1) // 2

Verification:

• $F=1$: $P=0$ (no padding needed)
• $F=3$: $P=1$
• $F=5$: $P=2$
• $F=15$: $P=7$

4. Common Pitfalls

• Using Float Division: return (F-1)/2 → 2.0 (not int).
• Assuming Even $F$: Code breaks (e.g., $F=4 \Rightarrow P=1.5$), but constraint prevents this.
• Off-by-One: Wrong formula like $P = F//2$ fails ($F=5 \Rightarrow 2$ correct, but $F=3 \Rightarrow 1$ correct vs $1$ wrong if $F//2=1$).
• Negative/Zero Input: Constraints ($1 \leq F \leq 15$, odd) prevent, but production code might add validation.
• Confusing Padding Types: "Same" assumes symmetric padding; asymmetric padding exists but not required here.

5. Time & Space Complexity

• Time: $O(1)$ — single arithmetic operation.
• Space: $O(1)$ — scalar input/output, no data structures.

Scalability: Independent of input size; formula generalizes beyond constraints to any odd $F$.