Apparatus and method for determining the Manhattan distance between two points

Claim 1

An apparatus for performing pattern recognition comprising: a memory storage area to store operands for execution; a first arithmetic logic pipeline coupled to the memory storage area for performing distance calculations between points of an unknown pattern and a reference pattern; and a second arithmetic logic pipeline coupled to the memory storage area for performing best path calculations between said points of said unknown pattern and said reference pattern, said second arithmetic logic pipeline executing in parallel with said first arithmetic logic pipeline; a first pointer pipeline associated with the first arithmetic pipeline for preparing pointer values for accessing memory to supply operand to the first arithmetic logic pipeline; a second pointer pipeline associated with the second arithmetic pipeline for preparing pointer values for accessing memory to supply operands to the second arithmetic logic pipeline wherein the first pointer pipeline and the second pointer pipeline operate in parallel with said first arithmetic pipeline and said second arithmetic pipeline; and wherein first arithmetic logic pipeline includes means for executing instructions to calculate distance between a first point in the unknown pattern and a second point in the reference pattern, the means for executing including: means for providing a first operand specified within a first instruction during a first instruction cycle and a third operand specified within a second instruction during a second instruction cycle immediately following the first instruction cycle; means for providing a second operand specified within said first instruction during a first instruction cycle and a fourth operand specified within the second arithmetic instruction during the second instruction cycle; first means coupled to receive the first operand and the second operand in the first instruction cycle for subtracting the first operand from the second operand to generate a first result during the first instruction cycle, wherein the first means is also coupled to receive the third operand and the fourth operand in the second instruction cycle for subtracting the third operand from the fourth operand to generate a third result during the second instruction cycle; second means coupled to receive the first operand and the second operand in the first instruction cycle for subtracting the second operand from the first operand to generate a second result during the first instruction cycle, wherein the second means is also coupled to receive the third operand and the fourth operand in the second instruction cycle for subtracting the fourth operand from the third operand to generate a fourth result during the second instruction cycle; and a multiplexer coupled to receive the first result and the second result during the first instruction cycle to select the positive of either the first result or the second result during the first instruction cycle, such that the absolute value of the difference between the first operand and the second operand is produced in the first instruction cycle, and wherein the multiplexer is also coupled to receive the third result and the fourth result during the second instruction cycle to select the positive of either the third result or the fourth result during the second instruction cycle, such that the absolute value of the difference between the third operand and the fourth operand is produced in the second instruction cycle, wherein the first pointer pipeline and the second pointer pipeline prepare pointer values during the first instruction cycle to allow the third operand and the fourth operand to be available at the second instruction cycle to the means for executing, wherein the first arithmetic pipeline calculates distance between the first point in the unknown pattern and the second point in the reference pattern in consecutive cycles.

Claim 2

An apparatus for performing pattern recognition comprising: a memory storage area to store operands for execution; a first arithmetic logic pipeline coupled to the memory storage area for performing distance calculations between points of an unknown pattern and a reference pattern; and a second arithmetic logic pipeline coupled to the memory storage area for performing best path calculations between said points of said unknown pattern and said reference pattern, said second arithmetic logic pipeline executing in parallel with said first arithmetic logic pipeline; a first pointer pipeline associated with the first arithmetic pipeline for preparing pointer values for accessing memory to supply operand to the first arithmetic logic pipeline; a second pointer pipeline associated with the second arithmetic pipeline for preparing pointer values for accessing memory to supply operands to the second arithmetic logic pipeline wherein the first pointer pipeline and the second pointer pipeline operate in parallel with said first arithmetic pipeline and said second arithmetic pipeline; and wherein first arithmetic logic pipeline includes means for executing instructions to calculate distance between a first point in the unknown pattern and a second point in the reference pattern, the means for executing including: means for providing a first operand specified within a first instruction during a first instruction cycle and a third operand specified within a second instruction during a second instruction cycle immediately following the first instruction cycle; means for providing a second operand specified within said first instruction during a first instruction cycle and a fourth operand specified within the second arithmetic instruction during the second instruction cycle; first means coupled to receive the first operand and the second operand in the first instruction cycle for subtracting the first operand from the second operand to generate a first result during the first instruction cycle, wherein the first means is also coupled to receive the third operand and the fourth operand in the second instruction cycle for subtracting the third operand from the fourth operand to generate a third result during the second instruction cycle; second means coupled to receive the first operand and the second operand in the first instruction cycle for subtracting the second operand from the first operand to generate a second result during the first instruction cycle, wherein the second means is also coupled to receive the third operand and the fourth operand in the second instruction cycle for subtracting the fourth operand from the third operand to generate a fourth result during the second instruction cycle; and a multiplexer coupled to receive the first result and the second result during the first instruction cycle to select the positive of either the first result or the second result during the first instruction cycle, such that the absolute value of the difference between the first operand and the second operand is produced in the first instruction cycle, and wherein the multiplexer is also coupled to receive the third result and the fourth result during the second instruction cycle to select the positive of either the third result or the fourth result during the second instruction cycle, such that the absolute value of the difference between the third operand and the fourth operand is produced in the second instruction cycle, wherein the first pointer pipeline and the second pointer pipeline prepare pointer values during the first instruction cycle to allow the third operand and the fourth operand to be available at the second instruction cycle to the means for executing, wherein the first arithmetic pipeline calculates distance between the first point in the unknown pattern and the second point in the reference pattern in consecutive cycles.

Claim 8

An apparatus for performing pattern recognition comprising: a memory storage area to store operands for execution; a first arithmetic logic pipeline coupled to the memory storage area for performing distance calculations between points of an unknown pattern and a reference pattern; and a second arithmetic logic pipeline coupled to the memory storage area for performing best path calculations between said points of said unknown pattern and said reference pattern, said second arithmetic logic pipeline executing in parallel with said first arithmetic logic pipeline; a first pointer pipeline associated with the first arithmetic pipeline for preparing pointer values for accessing memory to supply operands to the first arithmetic logic pipeline; a second pointer pipeline associated with the second arithmetic pipeline for preparing pointer values for accessing memory to supply operands to the second arithmetic logic pipeline, wherein the first pointer pipeline and the second pointer pipeline operate in parallel with said first arithmetic pipeline and said second arithmetic pipeline; and wherein first arithmetic logic pipeline includes means for executing instructions to calculate distance between a first point in the unknown pattern and a second point in the reference pattern, the means for executing including: means for providing a first operand specified within a first instruction during a first instruction cycle and a third operand specified within a second instruction during a second instruction cycle immediately following the first instruction cycle; means for providing a second operand specified within said first instruction during a first instruction cycle and a fourth operand specified within the second arithmetic instruction during the second instruction cycle; a first arithmetic logic unit coupled to receive the first operand and the second operand in the first instruction cycle to subtract the first operand from the second operand to generate a first result during the first instruction cycle, wherein the first arithmetic logic unit is also coupled to receive the third operand and the fourth operand in the second instruction cycle to subtract the third operand from the fourth operand to generate a third result during the second instruction cycle; a second arithmetic logic unit coupled to receive the first operand and the second operand in the first instruction cycle to subtract the second operand from the first operand to generate a second result during the first instruction cycle, wherein the second arithmetic logic unit is also coupled to receive the third operand and the fourth operand in the second instruction cycle to subtract the fourth operand from the third operand to generate a fourth result during the second instruction cycle; and a multiplexer coupled to receive the first result and the second result during the first instruction cycle to select the positive of either the first result or the second result during the first instruction cycle, such that the absolute value of the difference between the first operand and the second operand is produced in the first instruction cycle, and wherein the multiplexer is also coupled to receive the third result and the fourth result during the second instruction cycle to select the positive of either the third result or the fourth result during the second instruction cycle, such that the absolute value of the difference between the third operand and the fourth operand is produced in the second instruction cycle, wherein the first pointer pipeline and the second pointer pipeline prepare pointer values during the first instruction cycle to allow the third operand and the fourth operand to be available at the second instruction cycle to the means for executing, wherein the first arithmetic pipeline calculates distance between the first point in the unknown pattern and the second point in the reference pattern in two consecutive cycles without a pointer update delay.

Claim 9

An apparatus for performing pattern recognition comprising: a memory storage area to store operands for execution; a first arithmetic logic pipeline coupled to the memory storage area for performing distance calculations between points of an unknown pattern and a reference pattern; and a second arithmetic logic pipeline coupled to the memory storage area for performing best path calculations between said points of said unknown pattern and said reference pattern, said second arithmetic logic pipeline executing in parallel with said first arithmetic logic pipeline; a first pointer pipeline associated with the first arithmetic pipeline for preparing pointer values for accessing memory to supply operands to the first arithmetic logic pipeline; a second pointer pipeline associated with the second arithmetic pipeline for preparing pointer values for accessing memory to supply operands to the second arithmetic logic pipeline, wherein the first pointer pipeline and the second pointer pipeline operate in parallel with said first arithmetic pipeline and said second arithmetic pipeline; and wherein first arithmetic logic pipeline includes means for executing instructions to calculate distance between a first point in the unknown pattern and a second point in the reference pattern, the means for executing including: means for providing a first operand specified within a first instruction during a first instruction cycle and a third operand specified within a second instruction during a second instruction cycle immediately following the first instruction cycle; means for providing a second operand specified within said first instruction during a first instruction cycle and a fourth operand specified within the second arithmetic instruction during the second instruction cycle; a first arithmetic logic unit coupled to receive the first operand and the second operand in the first instruction cycle to subtract the first operand from the second operand to generate a first result during the first instruction cycle, wherein the first arithmetic logic unit is also coupled to receive the third operand and the fourth operand in the second instruction cycle to subtract the third operand from the fourth operand to generate a third result during the second instruction cycle; a second arithmetic logic unit coupled to receive the first operand and the second operand in the first instruction cycle to subtract the second operand from the first operand to generate a second result during the first instruction cycle, wherein the second arithmetic logic unit is also coupled to receive the third operand and the fourth operand in the second instruction cycle to subtract the fourth operand from the third operand to generate a fourth result during the second instruction cycle; and a multiplexer coupled to receive the first result and the second result during the first instruction cycle to select the positive of either the first result or the second result during the first instruction cycle, such that the absolute value of the difference between the first operand and the second operand is produced in the first instruction cycle, and wherein the multiplexer is also coupled to receive the third result and the fourth result during the second instruction cycle to select the positive of either the third result or the fourth result during the second instruction cycle, such that the absolute value of the difference between the third operand and the fourth operand is produced in the second instruction cycle, wherein the first pointer pipeline and the second pointer pipeline prepare pointer values during the first instruction cycle to allow the third operand and the fourth operand to be available at the second instruction cycle to the means for executing, wherein the first arithmetic pipeline calculates distance between the first point in the unknown pattern and the second point in the reference pattern in two consecutive cycles without a pointer update delay.

Claim 14

A system performing pattern recognition comprising: a bus to provide a communication pathway between system components; a central processor coupled to said bus; and a pattern recognition mechanism coupled to said bus, wherein said pattern recognition mechanism further comprises a memory storage area to store operands for execution; a first arithmetic logic pipeline coupled to the memory storage area for performing distance calculations between points of an unknown pattern and a reference pattern; and a second arithmetic logic pipeline coupled to the memory storage area for performing best path calculations between said points of said unknown pattern and said reference pattern, said second arithmetic logic pipeline executing in parallel with said first arithmetic logic pipeline; a first pointer pipeline associated with the first arithmetic pipeline for preparing pointer values for accessing memory to supply operands to the first arithmetic logic pipeline; a second pointer pipeline associated with the second arithmetic pipeline for preparing pointer values for accessing memory to supply operands to the second arithmetic logic pipeline, wherein the first pointer pipeline and the second pointer pipeline operate in parallel with said first arithmetic pipeline and said second arithmetic pipeline; and wherein first arithmetic logic pipeline includes means for executing instructions to calculate distance between a first point in the unknown pattern and a second point in the reference pattern, the means for executing including: means for providing a first operand specified within a first instruction during a first instruction cycle and a third operand specified within a second instruction during a second instruction cycle immediately following the first instruction cycle; means for providing a second operand specified within said first instruction during a first instruction cycle and a fourth operand specified within the second arithmetic instruction during the second instruction cycle; first means coupled to receive the first operand and the second operand in the first instruction cycle for subtracting the first operand from the second operand to generate a first result during the first instruction cycle, wherein the first means is also coupled to receive the third operand and the fourth operand in the second instruction cycle for subtracting the third operand from the fourth operand to generate a third result during the second instruction cycle; second means coupled to receive the first operand and the second operand in the first instruction cycle for subtracting the second operand from the first operand to generate a second result during the first instruction cycle, wherein the second means is also coupled to receive the third operand and the fourth operand in the second instruction cycle for subtracting the fourth operand from the third operand to generate a fourth result during the second instruction cycle; and a multiplexer coupled to receive the first result and the second result during the first instruction cycle to select the positive of either the first result or the second result during the first instruction cycle, such that the absolute value of the difference between the first operand and the second operand is produced in the first instruction cycle, and wherein the multiplexer is also coupled to receive the third result and the fourth result during the second instruction cycle to select the positive of either the third result or the fourth result during the second instruction cycle, such that the absolute value of the difference between the third operand and the fourth operand is produced in the second instruction cycle, wherein the first pointer pipeline and the second pointer pipeline prepare pointer values during the first instruction cycle to allow the third operand and the fourth operand to be available at the second instruction cycle to the means for executing, wherein the first arithmetic pipeline calculates distance between the first point in the unknown pattern and the second point in the reference pattern in consecutive cycles.

Claim 15

A system performing pattern recognition comprising: a bus to provide a communication pathway between system components; a central processor coupled to said bus; and a pattern recognition mechanism coupled to said bus, wherein said pattern recognition mechanism further comprises a memory storage area to store operands for execution; a first arithmetic logic pipeline coupled to the memory storage area for performing distance calculations between points of an unknown pattern and a reference pattern; and a second arithmetic logic pipeline coupled to the memory storage area for performing best path calculations between said points of said unknown pattern and said reference pattern, said second arithmetic logic pipeline executing in parallel with said first arithmetic logic pipeline; a first pointer pipeline associated with the first arithmetic pipeline for preparing pointer values for accessing memory to supply operands to the first arithmetic logic pipeline; a second pointer pipeline associated with the second arithmetic pipeline for preparing pointer values for accessing memory to supply operands to the second arithmetic logic pipeline, wherein the first pointer pipeline and the second pointer pipeline operate in parallel with said first arithmetic pipeline and said second arithmetic pipeline; and wherein first arithmetic logic pipeline includes means for executing instructions to calculate distance between a first point in the unknown pattern and a second point in the reference pattern, the means for executing including: means for providing a first operand specified within a first instruction during a first instruction cycle and a third operand specified within a second instruction during a second instruction cycle immediately following the first instruction cycle; means for providing a second operand specified within said first instruction during a first instruction cycle and a fourth operand specified within the second arithmetic instruction during the second instruction cycle; first means coupled to receive the first operand and the second operand in the first instruction cycle for subtracting the first operand from the second operand to generate a first result during the first instruction cycle, wherein the first means is also coupled to receive the third operand and the fourth operand in the second instruction cycle for subtracting the third operand from the fourth operand to generate a third result during the second instruction cycle; second means coupled to receive the first operand and the second operand in the first instruction cycle for subtracting the second operand from the first operand to generate a second result during the first instruction cycle, wherein the second means is also coupled to receive the third operand and the fourth operand in the second instruction cycle for subtracting the fourth operand from the third operand to generate a fourth result during the second instruction cycle; and a multiplexer coupled to receive the first result and the second result during the first instruction cycle to select the positive of either the first result or the second result during the first instruction cycle, such that the absolute value of the difference between the first operand and the second operand is produced in the first instruction cycle, and wherein the multiplexer is also coupled to receive the third result and the fourth result during the second instruction cycle to select the positive of either the third result or the fourth result during the second instruction cycle, such that the absolute value of the difference between the third operand and the fourth operand is produced in the second instruction cycle, wherein the first pointer pipeline and the second pointer pipeline prepare pointer values during the first instruction cycle to allow the third operand and the fourth operand to be available at the second instruction cycle to the means for executing, wherein the first arithmetic pipeline calculates distance between the first point in the unknown pattern and the second point in the reference pattern in consecutive cycles.