International Business Machines Corporation

David Curtis Van Voorhis

Thomas Harvey Morrin

Gordon Taylor Davis

Baiju Dhirajlal Mandalia

Jan W Van Den Berg

Robert E Landa

A special purpose communications protocol processor (CPP) provides more efficient processing of layered communications protocols--e.g. SNA (Systems Network Architecture) and OSI (Open Systems Interconnection)--than contemporary general purpose processors, permitting hitherto unavailable operations relative to high speed communication links. The CPP contains special-purpose circuits dedicated to quick performance (e.g. single machine cycle execution) of functions needed to process header and frame information, such functions and information being of the sort repeatedly encountered in all protocol layers, and uses instructions architected to operate these circuits. The header processing functions given special treatment in this manner include priority branch determination functions, register bit reshaping (rearranging) functions, and instruction address processing functions. Frame processing functions so handled include CRC (cyclic redundancy check) computations, bit insertion/deletion operations and special character detection operations.

Specialized communications processor for layered protocols

A major/minor loop bubble memory configuration that provides gap free serial access to the data in the minor loops and which maintains the non-volatility of data when subjected to a power-on-off-on sequence. The configuration includes a timing minor loop in combination with the data storage minor loops in the major/minor loop array. The placement of a single timing bubble within the timing loop permits gap free serial access to the data in the remaining storage minor loops.

Major/minor loop bubble memory with timing loop

A random access bubble memory directs a plurality of continuous streams of bubbles toward a plurality of storage loops. A write decoder selects one continuous stream of bubbles. An annihilator then transforms this one continuous stream of bubbles into the desired data pattern which is then stored in a selected loop. While the data pattern is being formed, a read decoder directs the data which had been stored in the selected loop to a bubble detector. This memory has a unified read/write cycle which permits intermixed read and write, read/modify/write, and swap operations. This bubble memory allows a user to remove power abruptly during a read/write cycle without returning a partially processed block to its storage loop and without saving the identity of the block. In a preferred embodiment, the read and write decoders are operated simultaneously by identical control currents.

Random access bubble memory with unified read/write cycle

A conventional word organized random access memory is modified for image processing operations so that the pq image points of any 1 .times. pq, pq .times. 1 or p.times.q subarray of an rp .times. sq or smaller image array stored in the memory can be extracted or updated in a single memory cycle. The invention contemplates pq + 1 memory modules labeled from 0 to pq for storing the image points, each module being capable of storing rs points in distinguishable cells, only one cell of which is randomly accessible in a single instant of time. The invention further contemplates accessing circuitry for causing each image point I(i,j) of an image array to be routed to or from a memory module M(i,j) according to the relative M(i,j) =(iq+j)//(pq+1), where the notation '//' denotes the remainder resulting from integer division. The accessing circuitry additionally causes image point I(i,j) to be stored into or retrieved from a cell location A(i,j) of module M(i,j ) according to the relation A(i,j)=(i/p)s + (j/q).

Method and apparatus for accessing horizontal sequences, vertical

Apparatus for converting the codewords of variable-length minimum-redundancy codes into corresponding fixed-length characters. The conversion process employs a two-step mapping wherein a codeword is first converted into a fixed-length integer, and then the integer is used to index a table of fixed-length characters. The apparatus for achieving this two-step mapping comprises table storage, summation circuitry, compare/combine circuitry, and control circuitry. The table storage holds two tables, a first table containing the fixed-length characters and a second table whose values uniquely identify the variable-length code. The compare/combine circuitry and the summation circuitry accept as input the successive bits of a codeword to be converted into its corresponding fixed-length character. As the successive codeword bits are received, the summation circuitry operates on elements of the second table to calculate successive values of a weighted sum and an unweighted sum. The compare/combine circuitry uses the successive values of the weighted sum to isolate the bits comprising the codeword. This codeword is then combined with the weighted sum and the unweighted sum to provide a fixed-length integer, and the integer is used to index the table of fixed-length characters.

Variable-length to fixed-length conversion of minimum-redundancy codes

A conventional word organized random access memory is modified for image processing operations so that the pq image points of any 1 .times. pq subarray, any pq .times. 1 subarray, or any regularly-spaced p .times. q subarray of an rp .times. sq or smaller image array stored in the memory can be extracted or updated in a single memory cycle. The invention contemplates pq memory modules labeled from 0 to pq-1 for storing the image points, each module being capable of storing rs points in distinguishable cells, only one cell of which is randomly accessible in a single instant of time. The invention further contemplates accessing circuitry for causing each image point I(i,j) of an image array to be routed to or from a memory module M(i,j) according to the relation M(i,j)=[iq+(i/p)//q+j]//pq, where the notations '/' and '//' denote, respectively, the quotient and the remainder resulting from integer division. The accessing circuitry additionally causes image point I(i,j ) to be stored into or retrieved from a cell location A(i,j) of module M(i,j) according to the relation A(i,j)=(i/p)s+(j/q).

A conventional word organized random access memory is modified for image processing operations so that the pq image points of any 1 .times. pq, pq .times. 1 or pxq subarray of an rp .times. sq or smaller image array stored in the memory can be extracted or updated in a single memory cycle. The invention contemplates 2 pq memory modules labeled from 0 to 2pq-1 for storing the image points, each module being capable of storing rs/2 points in distinguishable cells, only one cell of which is randomly accessible in a single instant of time. The invention further contemplates accessing circuitry for causing each image point I(i,j) of an image array to be routed to or from a memory module M(i,j) according to the relation M(i,j)=pq[(i/p)//2]+ (iq+i/2p+j)//pq, where the notations '/' and '//' denote, respectively, the quotient and the remainder resulting from integer division. The accessing circuitry additionally causes image point I(i,j) to be stored into or retrieved from a cell location A(i,j) of module M(i,j) according to the relation A(i,j)=(i/2p)s+(j/q).

Apparatus for encoding ordinary run-length codes and run-length codes that have been extended to include two classes of code words, regular code words for runs and special code words for selected special situations. The encoder comprises table storage, select/combine circuitry, and shift-out circuitry. The table storage holds four small tables whose values can be adjusted to correspond to any ordinary or extended run-length code to be implemented. The select/combine circuitry accepts as input a binary value that uniquely identifies the desired code word, and combines this binary value with selected table values to calculate the desired code word. The code word bits are then outputted sequentially by the shift-out circuitry.

Apparatus for encoding extended run-length codes

A conventional word organized random access memory is modified for image processing operations so that the pq image points of any 1 .times. pq or p .times. q subarray of an rp .times. sq or smaller image array stored in the memory can be extracted or updated in a single memory cycle. The invention contemplates pq memory modules labeled from 0 to pq-1 for storing the image points, each module being able to store rs points in distinguishable cells, only one cell of which is randomly accessible in a single instant of time. The invention further contemplates accessing circuitry for causing each image point I(i,j) of an image array to be routed to or from a memory module M(i,j) according to the relation M(i,j)=(iq+j)//pq, where (iq+j)//pq is the remainder resulting from the integer division of (iq+j) by pq. The accessing circuitry additionally causes image point I(i,j) to be stored into or retrieved from a cell location A(i,j) of module M(i,j) according to the relation A(i,j)=(i/p)s+(j/q), where i/p and j/q represent integer quotients.

Growing community of inventors

Los Gatos, CA, United States of America

David Curtis Van Voorhis