Heading bias effects in PNS using IMUs attached to shoes are analyzed in this paper. The navigation algorithms of a single foot PNS where one IMU is attached to a foot and dual foot PNSs where two IMUs are attached to each foot are derived. Two navigation algorithms are proposed for the dual foot PNS: 1) the positions from the independent right and left foot PNSs are averaged to provide the final position, 2) the right and left foot PNSs are correlated and it provides positions of each foot. Furthermore, it is proven that two methods are equal. Using the derived navigation algorithms the effect of heading bias caused by a misalignment of the moving direction and IMU is analyzed. The analysis explains the position error of a single foot PNS is diverged while the heading bias is effectively compensated in dual foot PNSs because of the symmetry of heading biases. The experimental results confirm the analysis.