OpenCores
URL https://opencores.org/ocsvn/pci_blue_interface/pci_blue_interface/trunk

Subversion Repositories pci_blue_interface

Compare Revisions

  • This comparison shows the changes necessary to convert path 
    /
    from Rev 65 to Rev 66
    ↔ Reverse comparison
  •

Rev 65 → Rev 66

/trunk/function_lib/wallace_tree_adder.v
0,0 → 1,274
//===========================================================================
// $Id: wallace_tree_adder.v,v 1.1 2001-08-31 11:23:37 bbeaver Exp $
//
// Copyright 2001 Blue Beaver. All Rights Reserved.
//
// Summary: Demonstrate how to use a Wallace Tree Adder to convert
// 3 binary numbers which need to be added into 2 binary
// numbers which need to be added ... without adding!
//
// This library is free software; you can distribute it and/or modify it
// under the terms of the GNU Lesser General Public License as published
// by the Free Software Foundation; either version 2.1 of the License, or
// (at your option) any later version.
//
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
// See the GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with this library. If not, write to
// Free Software Foundation, Inc.
// 59 Temple Place, Suite 330
// Boston, MA 02111-1307 USA
//
// Author's note about this license: The intention of the Author and of
// the Gnu Lesser General Public License is that users should be able to
// use this code for any purpose, including combining it with other source
// code, combining it with other logic, translated it into a gate-level
// representation, or projected it into gates in a programmable or
// hardwired chip, as long as the users of the resulting source, compiled
// source, or chip are given the means to get a copy of this source code
// with no new restrictions on redistribution of this source.
//
// If you make changes, even substantial changes, to this code, or use
// substantial parts of this code as an inseparable part of another work
// of authorship, the users of the resulting IP must be given the means
// to get a copy of the modified or combined source code, with no new
// restrictions on redistribution of the resulting source.
//
// Separate parts of the combined source code, compiled code, or chip,
// which are NOT derived from this source code do NOT need to be offered
// to the final user of the chip merely because they are used in
// combination with this code. Other code is not forced to fall under
// the GNU Lesser General Public License when it is linked to this code.
// The license terms of other source code linked to this code might require
// that it NOT be made available to users. The GNU Lesser General Public
// License does not prevent this code from being used in such a situation,
// as long as the user of the resulting IP is given the means to get a
// copy of this component of the IP with no new restrictions on
// redistribution of this source.
//
// This code was developed using VeriLogger Pro, by Synapticad.
// Their support is greatly appreciated.
//
// NOTE: I am not sure if a Carry-Save Adder is a Wallace Tree Adder,
// or if a Wallace Tree Adder is a Carry-Save Adder. Sorry.
//
// NOTE: The idea of a 3-input Wallace Tree is very simple.
// Start witb 3 N-Bit numbers to be added together.
// You can do that with 2 full adders, resulting in
// an N + 2 bit result.
// But notice that in each bit location, there are 3
// bits to be added. There can be 0, 1, 2, or 3 bits
// set to 1 in the 3 operands.
// 0, 1, 2, 3 can be represented as a 2-bit number!
// It is possible to reduce the 3 numbers to 2 numbers
// which later are added together to form the final sum.
// And you can interate this trick to add up more numbers.
//
// NOTE: A 3:2 Compression Adder seems to have a simple truth table.
// A B C Carry Data
// 0 0 0 0 0
// 0 0 1 0 1
// 0 1 0 0 1
// 1 0 0 0 1
// 0 1 1 1 0
// 1 0 1 1 0
// 1 1 0 1 0
// 1 1 1 1 1
// Look familiar? It's a full adder!
//
// NOTE: You could also add up to 7 numbers together by considering
// each bit location by itself, and using 3 binary weighted
// result bits to encode the 0 to 7 bits set in the inputs.
// You would then have to add the 3 numbers together to get the
// final result.
//
// NOTE: Reducing 3 numbers to 2 is done by a 3:2 Compression Adder.
// It also seems to be called a Carry-Save adder.
// Reducing 7 numbers to 3 is done by a 7:3 Compression Adder.
//
// NOTE: What if you want to add 4 numbers together? You might use
// the 7:3 compression adder. Too easy!
// Instead, you can do a trick. In each bit column, you can
// have a carry out which goes to the next column.
// Each bit column has 4 inputs plus the carry in from it's right.
// Each bit column has 2 outputs plus the carry out to it's left.
// Ignoring the Carry In for a second, there can be 0, 1, 2, 3, or 4
// bits set in each bit location amongst the 4 numbers begin added.
// The outputs of the block have weight 2 for carry, then 1 for data.
// That gives enough bits to represent 0, 1, 2, or 3 bits set.
// If 4 bits are set, you have to generate a carry to the next
// higher bit column. But since each bit in column N+1 represents
// 2 times as much as the bits in column N, you can only send
// carries representing carries by 2 over there.
// In bit column N+1, if you get a carry in, that is the same
// as having a 5th input. Now you have to represent 0 .. 5.
// Again, with 2 binary weighted output bits, you can only
// represent 0, 1, 2, or 3. To get 4 and 5, you have to
// send a carry to the NEXT higher bit. But notice that
// you have to send a carry indicating an excess of 2 bits
// set in the 5 inputs. Fortunately, 5 = 3 + 2, so you
// can represent all the values you need.
//
// NOTE: This can be written up as a truth table.
// The first column is the number of 1 bits set in the 4 input
// numbers. The second column is the carry in from the bit
// column to the right (LSB). The third column is the carry
// out to the bit column to the left (MSB). The next column
// is the carry out to the final adder, and the last column is
// the data bit to the final adder. A 4:2 Compression Adder:
//
// Num_Set Carry_In Carry_Out Carry Sum
// 0 0 0 0 0 // 0
// 1 0 0 0 1 // 1
// 2 0 0 1 0 // 2 (*)
// 3 0 1 0 1 // 1 + 2 carried to next bit
// 4 0 1 1 0 // 2 + 2 carried to next bit
// 0 1 0 0 1 // 1
// 1 1 0 1 0 // 2
// 2 1 0 1 1 // 3 (*)
// 3 1 1 1 0 // 2 + 2 carried to next bit
// 4 1 1 1 1 // 3 + 2 carried to next bit
//
// The two rows with (*) can have Carry_Out set instead of Carry, as long
// as the two rows are the same.
// This truth table has the feature that Carry_Out is NOT a function
// of Carry_In. It strictly depends on Num_Set. So a giant array
// of these 4:2 Compressor Adders do not result in a ripple carry.
//
// NOTE: All that seems complicated.
// An extremely simple way to look at this is to consider the inputs
// A, B, and C as going into a 3:2 Compression Adder. The Carry output
// is sent to the next bit column as Carry_out.
// The Data Output from the ABC adder plus the D input plus the Carry_in
// input are sent to a second 3:2 Compression Adder. The outputs of
// that second adder are the Carry and Data output for the 4:2
// Compression Adder.
// This circuit makes it clear that a ripple carry can't occur. The
// Carry_out is only a function of A, B, and C. The Carry_in
// signal combines with the D input and the Data_out from the ABC
// adder, resulting in the final Carry and Data signals.
//
// NOTE: If the 4:2 Compression Adder is implemented as 2 cascaded 3:2 Compression
// Adders, a new truth table is used. It's actually the SAME truth table,
// except the (*) terms are chosen to use BOTH encodings when appropriate.
//
// ABC_Set Carry_Out D Carry_In Carry Sum
// 0 0 0 0 0 0 // 0
// 1 0 0 0 0 1 // 1
// 2 1 0 0 0 0 // 2 (*)
// 3 1 0 0 0 1 // 1 + 2 carried to next bit
// 0 0 1 0 0 1 // 1
// 1 0 1 0 1 0 // 2 (*)
// 2 1 1 0 0 1 // 1 + 2 carried to next bit
// 3 1 1 0 1 0 // 2 + 2 carried to next bit
// 0 0 0 1 0 1 // 1
// 1 0 0 1 1 0 // 2
// 2 1 0 1 0 1 // 3 (*)
// 3 1 0 1 1 0 // 2 + 2 carried to next bit
// 0 0 1 1 1 0 // 2
// 1 0 1 1 1 1 // 3 (*)
// 2 1 1 1 1 0 // 2 + 2 carried to next bit
// 3 1 1 1 1 1 // 3 + 2 carried to next bit
//
// NOTE: So what if you want to add more numbers together than just 3? Say 9!
// You can iterate this idea. You can use a 3:2 Compression Adder to
// reduce each group of 3 operands to 2. You have 6 numbers remaining
// to add.
// You can take each group of 3 numbers from that 6 and apply another
// 3:2 Compression Adder to it, resulting in a total of 4 numbers to add.
// You can then do the tricky 4:2 Compression Adder to get down to 2 numbers.
// Finally, use the best adder you have to add up the last 2 numbers.
//
// NOTE: You might instead use 2 4:2 Compression Adders to drop the original
// 9 numbers to 2 + 2 + 1. Then use another 4:2 Compression Adder
// to get down to 2 + 1 operands. Use a 3:2 Compression Adder, and
// a final fast adder to add up the last 2 numbers.
//
// NOTE: When using the outputs of one set of Compression Adders as inputs
// to another set of Compression Adders, make sure that the bits
// with corresponding weights are added together.
// It seems that using 3:2 Compression Adders results in long lines
// as the layers of adders are hooked together, while 4:2 Compression
// Adders hook up regularly. I don't know if this is actually true.
//
// NOTE: A 3:2 Compression Adder would fit in a CLB easily.
// A 4:2 Compression Adder would not fit. Too many outputs.
//
//===========================================================================
 
`timescale 1ns/1ps
 
// NOTE: This might be in a vendor-supplied library element.
module compression_adder_3_2_slice_private (
A_in, B_in, C_in,
Data_out, Carry_out
);
input A_in;
input B_in;
input C_in;
output Data_out;
output Carry_out;
 
assign Data_out = A_in ^ B_in ^ C_in;
assign Carry_out = (A_in & B_in) | (A_in & C_in) | (B_in & C_in);
endmodule
 
// A 4:2 Compression Adder seems more complicated. One way to look at it
// is as 2 cascaded 3:2 Compression Adders. Is this the minimum logic way?
 
module compression_adder_4_2_slice_private (
A_in, B_in, C_in, D_in, Carry_in_right,
Data_out, Carry_out, Carry_out_left
);
input A_in, B_in, C_in;
output Data_out, Carry_out, Carry_out_left;
 
// First 3:2 Compression Adder
wire E_in = A_in ^ B_in ^ C_in; // latest I think
assign Carry_out_left = (A_in & B_in) | (A_in & C_in) | (B_in & C_in);
 
// Second 3:2 Compression Adder
assign Data_out = E_in ^ (D_in ^ Carry_in_right); // parens for speed?
assign Carry_out = (E_in & (D_in | Carry_in_right)) | (D_in & Carry_in_right);
endmodule
 
// NOTE: WORKING:
module wallace_tree_adder_3_2 (
A_in, B_in, C_in,
Data_out
);
parameter OPERAND_WIDTH = 0;
 
input [OPERAND_WIDTH - 1 : 0] A_in;
input [OPERAND_WIDTH - 1 : 0] B_in;
input [OPERAND_WIDTH - 1 : 0] C_in;
output [OPERAND_WIDTH + 1 : 0] Data_out;
 
assign Data_out[OPERAND_WIDTH - 1 : 0] = A_in[OPERAND_WIDTH - 1 : 0]
+ B_in[OPERAND_WIDTH - 1 : 0]; // just kidding!
assign Carry_out[OPERAND_WIDTH : 1] = C_in[OPERAND_WIDTH - 1 : 0];
endmodule
 
// NOTE: WORKING:
module wallace_tree_adder_4_2 (
A_in, B_in, C_in, D_in,
Data_out
);
parameter OPERAND_WIDTH = 0;
 
input [OPERAND_WIDTH - 1 : 0] A_in;
input [OPERAND_WIDTH - 1 : 0] B_in;
input [OPERAND_WIDTH - 1 : 0] C_in;
input [OPERAND_WIDTH - 1 : 0] D_in;
output [OPERAND_WIDTH + 1 : 0] Data_out;
 
assign Y_out[OPERAND_WIDTH - 1 : 0] = A_in[OPERAND_WIDTH - 1 : 0]
+ B_in[OPERAND_WIDTH - 1 : 0]; // just kidding!
assign Z_out[OPERAND_WIDTH - 1 : 0] = C_in[OPERAND_WIDTH - 1 : 0]
+ D_in[OPERAND_WIDTH - 1 : 0]; // just kidding!
endmodule
 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.