An image can be represented by a two-dimensional array of "image points," which are sets of integers that each describe the color and intensity of a portion of the image. Image-processing operations require that an image or partial image be stored in a memory system that permits access to sequences of image points along any row or column of this image array and/or to the image points within small rectangular areas of the array. This paper describes a number of memory systems that permit access to 1 × pq,pq × 1 and/or p × q subarrays of an image array, where p and q are design parameters.

In the above correspondence1 a three-step algorithm is presented for transposing large nonsquare matrices stored externally or in main memory. The first step can be generalized, and the last two steps can be replaced with a single step.

Most of the data compression strategies currently used for black/white (one-bit gray-scale) images involve the detection and noiseless encoding of a specified set of image features, the most common features being "runs" of adjacent equal.valued picture elements. A procedure is provided that, given the frequency distribution for a particular set of features in a sample of images, calculates an extended run-length code (ERLC) that includes two classes of codewords: "regular" codewords for the runs and "special" codewords for the other image features. An ERLC is shown to be highly efficient for the sample images, uniformly efficient for similar images not in the sample, and easily implemented. An encoder and the corresponding decoder are described which can implement any ERLC that includes up toRregular codewords andSspecial codewords, whereRandSare design parameters. Neither the encoder nor the decoder requires a table of codewords; rather, both are controlled by two auxiliary tables that include only\ell_{max} [\log_{2} R]-bit entries and\ell_{max} [\log_{2} S]-bit entries, respectively, where\ell_{max}is the length of the longest codeword.

LetP(i)= (1 - \theta)\theta^ibe a probability assignment on the set of nonnegative integers where\thetais an arbitrary real number,0 < \theta < 1. We show that an optimal binary source code for this probability assignment is constructed as follows. Letlbe the integer satisfying\theta^l + \theta^{l+1} \leq 1 < \theta^l + \theta^{l-1}and represent each nonnegative integeriasi = lj + rwhenj = \lfloor i/l \rfloor, the integer part ofi/l, andr = [i] mod l. Encodejby a unary code (i.e.,jzeros followed by a single one), and encoderby a Huffman code, using codewords of length\lfloor \log_2 l \rfloor, forr < 2^{\lfloor \log l+1 \rfloor} - l, and length\lfloor \log_2 l \rfloor + 1otherwise. An optimal code for the nonnegative integers is the concatenation of those two codes.

An algorithm is described where given the letter probabilities for a memoryless message source that emitsNletters, onlyO(N^2)steps are required--rather than the previously reportedO(N^3)steps---to construct a code with the minimum average codeword length permitted by the constraint that codeword lengths be monotonically increasing.

When the letter probabilitiesp_1,p_2,\cdots,p_Nfor a message sourceSare unknown, it may be imprudent to construct a Huffman code forSbased on the relative frequenciesf_1, f_2,\cdots, f_Nof the letters in a sample messageM. Rather, a more cautious approach is to select an integerb \geq \log_2 Nand to construct the codeC_bwhich encodesMmost efficiently subject to the restriction that codewords are at mostbbits long. This correspondence describes an algorithm for calculatingC_binO((b-\log_2 N)N^2)steps.

The minimum number of comparators S(N) required by an N-input sorting network is bounded below by S(N) ≥ N[log2(N) - 1] + 0(1), as a consequence of the theorem S(N) ≥ S(N - 1) + [log2(N)].