We propose a parallel architecture for implementing the interpolation step in the Koetter-Vardy soft-decision Reed-Solomon decoding algorithm. The key feature is the embedding of both a binary tree and a linear array into a two-dimensional array processor enabling fast polynomial evaluation operations. An FPGA interpolation processor was implemented and demonstrated at a clock frequency of 23 MHz, corresponding to decoding rates of 10-15 Mbps.