Memory addressing circuit for converting sequential input data to interleaved output data sequence using multiple memories

A system as in clam 2 in which said means for reading comprises:

• means for computing the storage distance increment I.sub.m between adjacent Rth stored words for the m.sup.th group of received data words assembled in terms of memory locations starting with the memory location containing the first R.sup.th data word and counting in a predetermined path along the memory locations of said N memories in said predetermined sequence and through successively increasing levels of said memory locations to the memory location containing the next R.sup.th data word, and in accordance with the expression:
• R.sup.m [MOD((T.multidot.R)-1)]
• where m is the m.sup.th group of data words measured from said first group of data words;
• means for computing the absolute address location A.sub.n of each of said R.sup.th words measured from a given memory location containing the first received data word of said first group of data words along said predetermined path to each of said R.sup.th words, and in accordance with the expression:
• A.sub.n =I.sub.m .multidot.(n-1)[MOD((T.multidot.R)-1)]
• where n is the n.sup.th one of the R.sup.th data words in the m.sup.th group of data words;
• means for computing the memory location level W.sub.n of each R.sup.th word to be read from said memories in accordance with the expression:
• W.sub.n =LOWEST NEXT INTEGER OF (1-A.sub.n /N);
• and
• means for computing the particular memory M.sub.n in which each R.sup.th word is stored in accordance with the expression:
• M.sub.n =A.sub.n -(W.sub.n -1)N+1.

A system for converting sequentially received data words, in each group of successively received groups of data words, into an interleaved output data word sequence, with each group of data words consisting of T successive series of R data words, said system comprising:

• N memories each having W.sub.n successive word location levels, where W.sub.n .multidot.N.gtoreq.T.multidot.R;
• first logic means for writing successive data words of a first group of data words into successive ones of said N memories in a predetermined sequence of said memories and in predetermined word location levels;
• second logic means for reading from said memories every R.sup.th data word of said first group of data words written into said memories to leave an available word location level in each instance where a data word was read therefrom;
• and
• said first logic means further constructed to write successively received data words of the next received group of data words and each of the subsequently received groups of data words into those particular word location levels which become available by the reading therefrom of the data words of the immediately preceding received group of data words, in the order in which the data words of said immediately preceding received group of data were read therefrom and as each of said particular word location levels become available;
• where T, R, and N have values such that no memory is accessed more than once for every S consecutive write-ins of data words therein, and where S is an integer greater than unity.

A method for converting sequentially received data words into an interleaved output data word sequence employing N separate memories and with the received data words being written serially into successive ones of said memories and being read therefrom in said interleaved manner, and in which said received data words are received as successive groups of data words with each group consisting of T sequentially received series of R data words, and comprising the steps of:

• forming said multiple memories into a matrix of memory locations having N columns each comprised of one of said separate memories, and having W.sub.n rows each comprised of a corresponding memory location from each of said N memories;
• storing the first received group of data words into successive memory locations of successively selected columns of memory locations;
• reading each successive R.sup.th data words from said successive memory locations with each successive memory location being in successively different columns of memory;
• storing the data words in subsequently received groups of data words in successive memory locations from which the data words of the immediately preceding group of data words were read in an interleaved manner and during the same time period that the data words of the immediately preceding group of data words were being read out;
• reading, in said interleaved manner, each successive R.sup.th stored data word of each subsequently received group of data words from the memory locations of said memory matrix and in a different column of memory than the column of memory into which a data word from the next following group of data words is currently being stored;
• and
• selecting T, R, N and W.sub.n such that no two successive R.sup.th data words are stored in the same column of memory locations.

In a system comprising N memories each having W successive word location levels, and means for selectively writing into and reading out of said memories, a method for converting sequentially received data words, in the form of successive groups of data words, into an interleaved output data word sequence, with each group of data words consisting of T successive series of R data words, and with W.multidot.N.gtoreq.T.multidot.R and comprising the steps of:

• writing successive data words of a first group of data words into successive ones of said memories in a predetermined sequence of said memories and in successively increasing word location levels;
• reading from memory every R.sup.th stored data word of said first group of data words and each subsequently received group of data words from said memories to leave an available word location level in each word location level from whence a data word was read;
• writing successively received data words of each of said subsequently received groups of data words into the available word location levels created by the reading therefrom of the data words of the immediately preceding group of data words and in the order in which the immediately preceding group of data words was read therefrom, but with the reading out of a data word and the writing in of a data not occurring simultaneously on the same word location;
• and
• selecting T, R, and N to have values such that no memory is accessed more than once for every S write-ins of data words therein, and where S is an integer greater than unity.