• Please review our updated Terms and Rules here

Right Hand Shift (RHS) of Bits using an ALU, 74F181

mmruzek

Experienced Member
Joined
Sep 28, 2011
Messages
227
Location
Michigan, USA
Hi, I am building a TTL computer using the 74F181 ALU. I am fairly far along in the project and I am coding now in machine code. One of the things that has come up as an issue pretty quickly is that there is no right hand bit shift available. The ALU has the usual ADD, Subtract, Increment, Decrement and many other logic functions, such as AND, NAND, OR, XOR, NOR, XNOR, NOT, etc.

My system data bus is 12 bits, so what would be especially useful is moving nibbles around. For example, moving the top nibble (the tribble?) to the bottom. Here is an example:

1011 0000 0000 becomes 0000 0000 1011

I could add some more hardware to do this, but my boards are already pretty jam-packed. The only way I have thought to do this in code is by doing a 16 case comparison. (4 bits = 16 cases).

Does anyone know any tricks using the math and logic functions to shift to the right? I'm not finding much with the search engines. Thanks! Michael

Here is a link to my project.

http://www.mtmscientific.com/stack.html
 
Other than two 8 bit parts with a latch and 3state output, I don't know of anything other than a bunch of left shifts.
Using some RAM, add to it self and move the carry bit in the output RAM location. That gives a loop of 4 to move things followed by an or operation to recombine. The output location need to be 0'd firrst, of course.
Dwight
 
If one of your functions is an end-around left rotate, you have your answer already. If you can test for carryout of an end-off left shift, you can synthesize a right shift by re-building the number from the carryouts and dropping the last iteration. Not pretty, but it's possible. If you don't have a way to check for carryouts, but can test for the presence of a 1 in the high-order bit, you can do the same--just test before shifting.

You could also test each bit individually without shifting and rebuild the result less the low-order bit. If you know ahead of time that your argument will tend to be range-restricted (i.e. less than 12 significant bits), you can shortcut some of the loop by testing for zeroes in groups of bits. None of these approaches is particularly wonderful in terms of cycles. You can also divide the operand into subfields and perform a table-lookup on each subfield and combine the results. On a 12 bit operand, you could divide the operand into 2 six-bit fields and perform table lookup in a 64-word table.

A simple left shift is, in my opinion, not as useful as a single right shift, given the presence of addition and subtraction. After all, a left shift of A is equivalent to computing A+A.

Note also, that I'm talking about a logical right shift, not an arithmetic sign-extension right shift.
 
Last edited:
How do you treat the most significant carry. If it goes to a register to be used in future operations you have what you need to do as Chuck and I have said.
Using Ti's notes on the 181.

C=0
F=A+A
F=A+A+C
F=A+A+C
F=A+A+C
F=A+0+C

6 steps in the micro code.
That should work.
Dwight
 
You guys put me on the right track! I have a Jump that uses the 12th bit as a flag, the Left shift using the Addition (A+A), and I can set the Least Significant Bit using the Increment instruction. All in a pretty tight loop. Thanks.

As an aside, what I would really enjoy tinkering with is a TTL barrel shifter. (A combinatorial circuit that does bit shifting without being clocked.) For some of my other jump instructions I am using the output from 74LS686, which does a real time equality and magnitude comparison of A and B in the ALU.

Michael
 
12-bits / PDP-8?!

This is one reason why the LD12 (PDP-8 lookalike) uses 74194s for the accumulator. The 74194 is a 4-bit bidirectional universal shift register with a parallel load. The 74181 chips perform the ALU functional unit and the accumulator register itself performs the rotate left and right independent of the ALU.

Dave
 
Only slightly off-the-subject, but if you're looking for a full-functioned ALU IC, you might want to look at the SN74S481 Described here. 48 pin DIP, with shift-left/right and a potload of other functionality, while still retaining the '181 basic functions. The DG Nova used several of these.
 
When I was first playing with my NC4000 processor ( a Stack processor ), I needed to chop 16 bit data into a byte value to send to 8 bit ports. I added two 74ls374s to swap bytes, rather than shifting the data in a loop. The NC4000 has a number of short addressing modes that only take one 16 bit for both the fetch/store and a short address.
By placing the address at FFFF, it only took 2 instructions to swap bytes, using -1, a short literal, as the target address. A nibble swap can be done the same way.

I like Dave's idea of using a 74194 ( 74LS194 is available ). It is just that it is still one clock per bit shift. Good for things like divide and multiply but still slow for real barrel shifting. There are a lot of specialized bit twizzlling that can be done as a specialized address, rather than a special microcode.
Dwight
 
Barrel shifters using MUXes, are neat but are logic hogs, which is why the 8080 had only single-bit shifts.

One approach uses 2:1 muxes in several stages, each stage selecting a shift by a certain number bits or pass-through. So, if you start with a stage that can either shift by one bit or none at the bottom, the next layer can be a shift by 2 bits or none, the next, by 4 bits or none and the final stage can shift by 8 bits or none. Note that you'll need 12 2:1 muxes for each stage. You see what I mean by "logic hog" for a single function...

However, as others have noted, a simple multi-bit, say 4 or 6 bits, shift function requires only a single stage of 12 muxes and can cut down on overhead considerably. One can also use a n-way MUX to select between, say, 0, 2 and 4 bit shifts.

Another logic hog is a "count the ones" tree. The CDC 6000 series had this instruction as a dedicated functional unit. I've been told that it was specifically requested by some (unnamed) intelligence agencies for crypto purposes.
 
Last edited:
Another logic hog is a "count the ones" tree. The CDC 6000 series had this instruction as a dedicated functional unit. I've been told that it was specifically requested by some (unnamed) intelligence agencies for crypto purposes.

And also why the Cray 1 had population count and leading zero count instructions.
 
Well, after all, the same guy (Seymour) designed both. "Count leading zeroes" is a subfunction of normalized floating point arithmetic, so less of a surprise.

The STAR, had arbitrary-length "count ones", "count leading equals" as well as a raft of other bit-oriented instructions--but then, memory was bit-addressable. It was a Thornton (he of the 6400) design.
 
Only slightly off-the-subject, but if you're looking for a full-functioned ALU IC, you might want to look at the SN74S481 Described here. 48 pin DIP, with shift-left/right and a potload of other functionality, while still retaining the '181 basic functions. The DG Nova used several of these.

That chip apparently used unobtainium technology. Can't find it anywhere other than on a data sheet!
 
They're around--they were expensive and not terribly plentiful. However, the Am2901 does pretty much the same thing and can still be found and is[/b] plentiful, comparatively. Cheap enough to cascade into a 12 bit ALU.
 
Back
Top