Search apparatus is described for locating an item which satisfies a predetermined criterion e.g. an instruction ready for execution or a free block of data. The apparatus uses a tree structure where each terminal node represents one of the items and is set if that item satisfies the criterion. A non-terminal node is set if any of its subordinate nodes is set. In order to locate an item, a path is traced through the tree, starting at the root node and passing through a series of set nodes until a set terminal node is reached.
An address decoding circuit for a functional block comprises branch portions serially connected with each other, in which a selecting signal is outputted on one of two output portions in accordance with the first bit information of an address signal when a selecting signal is applied to the first stage branch portion. The second stage output portion, to which the selecting signal is applied, outputs a selecting signal on one of two output portions in response to the second bit information of the address signal, in accordance with the selecting signal. Thereafter, each branch portion of the third to last stages outputs a selecting signal on one of two output portions in response to respective contents of the third bit to last bit of the address signal in accordance with the selecting signal applied from the preceding stage. By this selecting signal, a memory cell as a functional block portion is selected and is activated.
Circuitry for serial read memory access utilizing a random starting address is disclosed. Fast read access is provided without upsetting the original data pattern stored in the memory core if the sequential read is terminated in midstream. After the last memory address is reached, the access automatically rolls over to the first address. The circuit provides both random and sequential access functions and allows the memory to be used as a shift register of variable length.
The present invention makes it possible to effectively encode/decode position information of leaves or nodes in tree-structured information by using a less amount of bits. The coding device according to the present invention includes a branching layer discriminating portion for identifying a hierarchical layer in which a leaf or node and a preceding leaf or node are separately branched and a position information coding portion for outputting a code corresponding to the identified hierarchical layer as a position information code for the leaf or node. Namely, merely information indicating a hierarchical layer in which a current leaf or node and a preceding leaf or node are separately branched is encoded as the position information of the leaf or node, thus increasing the efficiency of encoding leaf or node positions in the tree-structured information.
A random access memory (1) is described in which one address of a row of addresses is activatable. There is also realized a block addressing mode in which all addresses between a selectable first address and a selectable second address are activated. To this end there are provided two address registers (4, 5) and a logic tree structure (8) which consists of modules. At each level of the tree structure a module receives a part of the information from the two address registers in order to determine, possibly co-controlled by information received from a higher level of the tree, whether one or both limit addresses are situated within the address range covered by the module and, if the answer is negative, to determine whether all addresses of this address range must be activated or remain deactivated.
Aspects for optimizing data searches in tree structures are described. The aspects include organizing multiple search levels of data into sub-trees contained in fixed size blocks of shared external memory of an embedded processing system, and requiring each reference to the data to proceed from one-half of a sub-tree during a descent of the search tree based on a search pattern.
