Here is a good tutorial explaining how convolutions work:
http://deeplearning.net/software/theano_versions/dev/tutorial/conv_arithmetic.html
Here is an example of a convolution with half (one) padding and stride 2
AI, Machine Learning and Deep Learning Blog