Hi,
I'm not going to tell you that it's doable and I'm not going to tell you that it's not but lets take a look at it.
The first issue, obviously, is memory. There's no 16F or 18F PIC available with >256kB memory, I think the most memory you can get in the 8bit ones is 128kB - so you're going to need an external memory of some sort.

The easiest to deal with probably is a SPI interfaced FLASH memory of some sort. They are cheap, available in a large array of sizes and they are cheap. EDIT: Did I say they are cheap ;-)

If the input and output "signals" are "random", ie the output values can not be retreived sequentially from the memory you're going to have to transfer perhaps 5 bytes to the memory to get 1 byte back - a total 40bits. Then you're going to have to do that 327680 times per second for a total average bitrate of 1.3Mbit / second. In reallity you're going to run the SPI faster than that - which is doable with the SPI peripheral in the PIC.

I have a feeling it might be doable but it obviously depends on what else the PIC needs to do. How are the "samples" ie. the index pointer for the lookuptable getting into the PIC?

More details please?

/Henrik.